<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span id="local-6989586621680816930"></span><span class="hs-comment">-- (c) The University of Glasgow 2006</span><span>
</span><span id="line-2"></span><span>
</span><span id="line-3"></span><span class="hs-pragma">{-# LANGUAGE CPP, ScopedTypeVariables, ViewPatterns #-}</span><span>
</span><span id="line-4"></span><span class="hs-pragma">{-# LANGUAGE GeneralizedNewtypeDeriving #-}</span><span>
</span><span id="line-5"></span><span>
</span><span id="line-6"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">GHC.Data.Graph.Directed</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-7"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier">Graph</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesOrd"><span class="hs-identifier">graphFromEdgedVerticesOrd</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesUniq"><span class="hs-identifier">graphFromEdgedVerticesUniq</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-8"></span><span>
</span><span id="line-9"></span><span>        </span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier">SCC</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier">Node</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#flattenSCC"><span class="hs-identifier">flattenSCC</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#flattenSCCs"><span class="hs-identifier">flattenSCCs</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-10"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompG"><span class="hs-identifier">stronglyConnCompG</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-11"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#topologicalSortG"><span class="hs-identifier">topologicalSortG</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-12"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#verticesG"><span class="hs-identifier">verticesG</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#edgesG"><span class="hs-identifier">edgesG</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#hasVertexG"><span class="hs-identifier">hasVertexG</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-13"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#reachableG"><span class="hs-identifier">reachableG</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#reachablesG"><span class="hs-identifier">reachablesG</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#transposeG"><span class="hs-identifier">transposeG</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-14"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#emptyG"><span class="hs-identifier">emptyG</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-15"></span><span>
</span><span id="line-16"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#findCycle"><span class="hs-identifier">findCycle</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-17"></span><span>
</span><span id="line-18"></span><span>        </span><span class="hs-comment">-- For backwards compatibility with the simpler version of Digraph</span><span>
</span><span id="line-19"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrd"><span class="hs-identifier">stronglyConnCompFromEdgedVerticesOrd</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-20"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrdR"><span class="hs-identifier">stronglyConnCompFromEdgedVerticesOrdR</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-21"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniq"><span class="hs-identifier">stronglyConnCompFromEdgedVerticesUniq</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-22"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniqR"><span class="hs-identifier">stronglyConnCompFromEdgedVerticesUniqR</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-23"></span><span>
</span><span id="line-24"></span><span>        </span><span class="hs-comment">-- Simple way to classify edges</span><span>
</span><span id="line-25"></span><span>        </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#EdgeType"><span class="hs-identifier">EdgeType</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#classifyEdges"><span class="hs-identifier">classifyEdges</span></a></span><span>
</span><span id="line-26"></span><span>    </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span class="hs-cpp">

#include &quot;HsVersions.h&quot;
</span><span>
</span><span id="line-30"></span><span class="hs-comment">------------------------------------------------------------------------------</span><span>
</span><span id="line-31"></span><span class="hs-comment">-- A version of the graph algorithms described in:</span><span>
</span><span id="line-32"></span><span class="hs-comment">--</span><span>
</span><span id="line-33"></span><span class="hs-comment">-- ``Lazy Depth-First Search and Linear IntGraph Algorithms in Haskell''</span><span>
</span><span id="line-34"></span><span class="hs-comment">--   by David King and John Launchbury</span><span>
</span><span id="line-35"></span><span class="hs-comment">--</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- Also included is some additional code for printing tree structures ...</span><span>
</span><span id="line-37"></span><span class="hs-comment">--</span><span>
</span><span id="line-38"></span><span class="hs-comment">-- If you ever find yourself in need of algorithms for classifying edges,</span><span>
</span><span id="line-39"></span><span class="hs-comment">-- or finding connected/biconnected components, consult the history; Sigbjorn</span><span>
</span><span id="line-40"></span><span class="hs-comment">-- Finne contributed some implementations in 1997, although we've since</span><span>
</span><span id="line-41"></span><span class="hs-comment">-- removed them since they were not used anywhere in GHC.</span><span>
</span><span id="line-42"></span><span class="hs-comment">------------------------------------------------------------------------------</span><span>
</span><span id="line-43"></span><span>
</span><span id="line-44"></span><span>
</span><span id="line-45"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Prelude.html"><span class="hs-identifier">GHC.Prelude</span></a></span><span>
</span><span id="line-46"></span><span>
</span><span id="line-47"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Utils.Misc.html"><span class="hs-identifier">GHC.Utils.Misc</span></a></span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Utils.Misc.html#minWith"><span class="hs-identifier">minWith</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Misc.html#count"><span class="hs-identifier">count</span></a></span><span> </span><span class="hs-special">)</span><span>
</span><span id="line-48"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html"><span class="hs-identifier">GHC.Utils.Outputable</span></a></span><span>
</span><span id="line-49"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Data.Maybe.html"><span class="hs-identifier">GHC.Data.Maybe</span></a></span><span> </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="GHC.Data.Maybe.html#expectJust"><span class="hs-identifier">expectJust</span></a></span><span> </span><span class="hs-special">)</span><span>
</span><span id="line-50"></span><span>
</span><span id="line-51"></span><span class="hs-comment">-- std interfaces</span><span>
</span><span id="line-52"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Maybe.html#"><span class="hs-identifier">Data.Maybe</span></a></span><span>
</span><span id="line-53"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../array/src/Data.Array.html#"><span class="hs-identifier">Data.Array</span></a></span><span>
</span><span id="line-54"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.List.html#"><span class="hs-identifier">Data.List</span></a></span><span> </span><span class="hs-keyword">hiding</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.OldList.html#transpose"><span class="hs-identifier">transpose</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-55"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Map.html#"><span class="hs-identifier">Data.Map</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Map</span></span><span>
</span><span id="line-56"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Set.html#"><span class="hs-identifier">Data.Set</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Set</span></span><span>
</span><span id="line-57"></span><span>
</span><span id="line-58"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#"><span class="hs-identifier">Data.Graph</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">G</span></span><span>
</span><span id="line-59"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#"><span class="hs-identifier">Data.Graph</span></a></span><span> </span><span class="hs-keyword">hiding</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier">Graph</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Edge"><span class="hs-identifier">Edge</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#transposeG"><span class="hs-identifier">transposeG</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#reachable"><span class="hs-identifier">reachable</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-60"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#"><span class="hs-identifier">Data.Tree</span></a></span><span>
</span><span id="line-61"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html"><span class="hs-identifier">GHC.Types.Unique</span></a></span><span>
</span><span id="line-62"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html"><span class="hs-identifier">GHC.Types.Unique.FM</span></a></span><span>
</span><span id="line-63"></span><span>
</span><span id="line-64"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      Graphs and Graph Construction
*                                                                      *
************************************************************************

Note [Nodes, keys, vertices]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 * A 'node' is a big blob of client-stuff

 * Each 'node' has a unique (client) 'key', but the latter
        is in Ord and has fast comparison

 * Digraph then maps each 'key' to a Vertex (Int) which is
        arranged densely in 0.n
-}</span><span>
</span><span id="line-81"></span><span>
</span><span id="line-82"></span><span class="hs-keyword">data</span><span> </span><span id="Graph"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span></span><span> </span><span id="local-6989586621680817140"><span class="annot"><a href="#local-6989586621680817140"><span class="hs-identifier hs-type">node</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Graph"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span></span><span> </span><span class="hs-special">{</span><span>
</span><span id="line-83"></span><span>    </span><span id="gr_int_graph"><span class="annot"><span class="annottext">forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span></span><span>      </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#IntGraph"><span class="hs-identifier hs-type">IntGraph</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-84"></span><span>    </span><span id="gr_vertex_to_node"><span class="annot"><span class="annottext">forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680817140"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-85"></span><span>    </span><span id="gr_node_to_vertex"><span class="annot"><span class="annottext">forall node. Graph node -&gt; node -&gt; Maybe Vertex
</span><a href="GHC.Data.Graph.Directed.html#gr_node_to_vertex"><span class="hs-identifier hs-var hs-var">gr_node_to_vertex</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621680817140"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span>
</span><span id="line-86"></span><span>  </span><span class="hs-special">}</span><span>
</span><span id="line-87"></span><span>
</span><span id="line-88"></span><span class="hs-keyword">data</span><span> </span><span id="Edge"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-var">Edge</span></a></span></span><span> </span><span id="local-6989586621680816982"><span class="annot"><a href="#local-6989586621680816982"><span class="hs-identifier hs-type">node</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Edge"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-var">Edge</span></a></span></span><span> </span><span class="annot"><a href="#local-6989586621680816982"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816982"><span class="hs-identifier hs-type">node</span></a></span><span>
</span><span id="line-89"></span><span>
</span><span id="line-90"></span><span class="hs-comment">{-| Representation for nodes of the Graph.

 * The @payload@ is user data, just carried around in this module

 * The @key@ is the node identifier.
   Key has an Ord instance for performance reasons.

 * The @[key]@ are the dependencies of the node;
   it's ok to have extra keys in the dependencies that
   are not the key of any Node in the graph
-}</span><span>
</span><span id="line-101"></span><span class="hs-keyword">data</span><span> </span><span id="Node"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-var">Node</span></a></span></span><span> </span><span id="local-6989586621680817135"><span class="annot"><a href="#local-6989586621680817135"><span class="hs-identifier hs-type">key</span></a></span></span><span> </span><span id="local-6989586621680817134"><span class="annot"><a href="#local-6989586621680817134"><span class="hs-identifier hs-type">payload</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="DigraphNode"><span class="annot"><a href="GHC.Data.Graph.Directed.html#DigraphNode"><span class="hs-identifier hs-var">DigraphNode</span></a></span></span><span> </span><span class="hs-special">{</span><span>
</span><span id="line-102"></span><span>      </span><span id="node_payload"><span class="annot"><span class="annottext">forall key payload. Node key payload -&gt; payload
</span><a href="GHC.Data.Graph.Directed.html#node_payload"><span class="hs-identifier hs-var hs-var">node_payload</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621680817134"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- ^ User data</span><span>
</span><span id="line-103"></span><span>      </span><span id="node_key"><span class="annot"><span class="annottext">forall key payload. Node key payload -&gt; key
</span><a href="GHC.Data.Graph.Directed.html#node_key"><span class="hs-identifier hs-var hs-var">node_key</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621680817135"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- ^ User defined node id</span><span>
</span><span id="line-104"></span><span>      </span><span id="node_dependencies"><span class="annot"><span class="annottext">forall key payload. Node key payload -&gt; [key]
</span><a href="GHC.Data.Graph.Directed.html#node_dependencies"><span class="hs-identifier hs-var hs-var">node_dependencies</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680817135"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-comment">-- ^ Dependencies/successors of the node</span><span>
</span><span id="line-105"></span><span>  </span><span class="hs-special">}</span><span>
</span><span id="line-106"></span><span>
</span><span id="line-107"></span><span>
</span><span id="line-108"></span><span id="local-6989586621680817124"><span id="local-6989586621680817125"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621680816889"><span class="hs-special">(</span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817125"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817124"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span>  </span><span class="annot"><a href="#local-6989586621680817125"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817124"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-109"></span><span>  </span><span id="local-6989586621680816883"><span class="annot"><span class="annottext">ppr :: Node a b -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var hs-var hs-var hs-var">ppr</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#DigraphNode"><span class="hs-identifier hs-type">DigraphNode</span></a></span><span> </span><span id="local-6989586621680816881"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680816881"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621680816880"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680816880"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span id="local-6989586621680816879"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680816879"><span class="hs-identifier hs-var">c</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b, a, [a]) -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621680816881"><span class="hs-identifier hs-var">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621680816880"><span class="hs-identifier hs-var">b</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621680816879"><span class="hs-identifier hs-var">c</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-110"></span><span>
</span><span id="line-111"></span><span id="local-6989586621680817119"><span class="annot"><a href="GHC.Data.Graph.Directed.html#emptyGraph"><span class="hs-identifier hs-type">emptyGraph</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817119"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-112"></span><span id="emptyGraph"><span class="annot"><span class="annottext">emptyGraph :: forall a. Graph a
</span><a href="GHC.Data.Graph.Directed.html#emptyGraph"><span class="hs-identifier hs-var hs-var">emptyGraph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; (Vertex -&gt; a) -&gt; (a -&gt; Maybe Vertex) -&gt; Graph a
forall node.
IntGraph
-&gt; (Vertex -&gt; node) -&gt; (node -&gt; Maybe Vertex) -&gt; Graph node
</span><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Vertex, Vertex) -&gt; [(Vertex, [Vertex])] -&gt; IntGraph
forall i e. Ix i =&gt; (i, i) -&gt; [(i, e)] -&gt; Array i e
</span><a href="../../base/src/GHC.Arr.html#array"><span class="hs-identifier hs-var">array</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">1</span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">0</span></span><span class="hs-special">)</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Char] -&gt; Vertex -&gt; a
forall a. HasCallStack =&gt; [Char] -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;emptyGraph&quot;</span></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Maybe Vertex -&gt; a -&gt; Maybe Vertex
forall a b. a -&gt; b -&gt; a
</span><a href="../../base/src/GHC.Base.html#const"><span class="hs-identifier hs-var">const</span></a></span><span> </span><span class="annot"><span class="annottext">Maybe Vertex
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-113"></span><span>
</span><span id="line-114"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-115"></span><span id="local-6989586621680817107"><span id="local-6989586621680817108"><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-type">graphFromEdgedVertices</span></a></span><span>
</span><span id="line-116"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#ReduceFn"><span class="hs-identifier hs-type">ReduceFn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817108"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817107"><span class="hs-identifier hs-type">payload</span></a></span><span>
</span><span id="line-117"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817108"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817107"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>           </span><span class="hs-comment">-- The graph; its ok for the</span><span>
</span><span id="line-118"></span><span>                                        </span><span class="hs-comment">-- out-list to contain keys which aren't</span><span>
</span><span id="line-119"></span><span>                                        </span><span class="hs-comment">-- a vertex key, they are ignored</span><span>
</span><span id="line-120"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817108"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817107"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-121"></span><span id="graphFromEdgedVertices"><span class="annot"><span class="annottext">graphFromEdgedVertices :: forall key payload.
ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var hs-var">graphFromEdgedVertices</span></a></span></span><span> </span><span id="local-6989586621680816866"><span class="annot"><span class="annottext">ReduceFn key payload
</span><a href="#local-6989586621680816866"><span class="hs-identifier hs-var">_reduceFn</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>            </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph (Node key payload)
forall a. Graph a
</span><a href="GHC.Data.Graph.Directed.html#emptyGraph"><span class="hs-identifier hs-var">emptyGraph</span></a></span><span>
</span><span id="line-122"></span><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var">graphFromEdgedVertices</span></a></span><span> </span><span id="local-6989586621680816865"><span class="annot"><span class="annottext">ReduceFn key payload
</span><a href="#local-6989586621680816865"><span class="hs-identifier hs-var">reduceFn</span></a></span></span><span> </span><span id="local-6989586621680816864"><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816864"><span class="hs-identifier hs-var">edged_vertices</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-123"></span><span>  </span><span class="annot"><span class="annottext">IntGraph
-&gt; (Vertex -&gt; Node key payload)
-&gt; (Node key payload -&gt; Maybe Vertex)
-&gt; Graph (Node key payload)
forall node.
IntGraph
-&gt; (Vertex -&gt; node) -&gt; (node -&gt; Maybe Vertex) -&gt; Graph node
</span><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816863"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Node key payload
</span><a href="#local-6989586621680816862"><span class="hs-identifier hs-var">vertex_fn</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Maybe Vertex
</span><a href="#local-6989586621680816861"><span class="hs-identifier hs-var">key_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">(key -&gt; Maybe Vertex)
-&gt; (Node key payload -&gt; key) -&gt; Node key payload -&gt; Maybe Vertex
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload -&gt; key
forall key payload. Node key payload -&gt; key
</span><a href="#local-6989586621680816859"><span class="hs-identifier hs-var">key_extractor</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-124"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816859"><span class="annot"><span class="annottext">key_extractor :: Node key payload -&gt; key
</span><a href="#local-6989586621680816859"><span class="hs-identifier hs-var hs-var">key_extractor</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Node key payload -&gt; key
forall key payload. Node key payload -&gt; key
</span><a href="GHC.Data.Graph.Directed.html#node_key"><span class="hs-identifier hs-var hs-var">node_key</span></a></span><span>
</span><span id="line-125"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621680816858"><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621680816858"><span class="hs-identifier hs-var">bounds</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816862"><span class="annot"><span class="annottext">Vertex -&gt; Node key payload
</span><a href="#local-6989586621680816862"><span class="hs-identifier hs-var">vertex_fn</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816861"><span class="annot"><span class="annottext">key -&gt; Maybe Vertex
</span><a href="#local-6989586621680816861"><span class="hs-identifier hs-var">key_vertex</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816857"><span class="annot"><span class="annottext">[(Vertex, Node key payload)]
</span><a href="#local-6989586621680816857"><span class="hs-identifier hs-var">numbered_nodes</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-126"></span><span>          </span><span class="annot"><span class="annottext">ReduceFn key payload
</span><a href="#local-6989586621680816865"><span class="hs-identifier hs-var">reduceFn</span></a></span><span> </span><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816864"><span class="hs-identifier hs-var">edged_vertices</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload -&gt; key
forall key payload. Node key payload -&gt; key
</span><a href="#local-6989586621680816859"><span class="hs-identifier hs-var">key_extractor</span></a></span><span>
</span><span id="line-127"></span><span>        </span><span id="local-6989586621680816863"><span class="annot"><span class="annottext">graph :: IntGraph
</span><a href="#local-6989586621680816863"><span class="hs-identifier hs-var hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex) -&gt; [(Vertex, [Vertex])] -&gt; IntGraph
forall i e. Ix i =&gt; (i, i) -&gt; [(i, e)] -&gt; Array i e
</span><a href="../../base/src/GHC.Arr.html#array"><span class="hs-identifier hs-var">array</span></a></span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621680816858"><span class="hs-identifier hs-var">bounds</span></a></span><span> </span><span class="hs-special">[</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816854"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[Vertex] -&gt; [Vertex]
forall a. Ord a =&gt; [a] -&gt; [a]
</span><a href="../../base/src/Data.OldList.html#sort"><span class="hs-identifier hs-var">sort</span></a></span><span> </span><span class="annot"><span class="annottext">([Vertex] -&gt; [Vertex]) -&gt; [Vertex] -&gt; [Vertex]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">(key -&gt; Maybe Vertex) -&gt; [key] -&gt; [Vertex]
forall a b. (a -&gt; Maybe b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/Data.Maybe.html#mapMaybe"><span class="hs-identifier hs-var">mapMaybe</span></a></span><span> </span><span class="annot"><span class="annottext">key -&gt; Maybe Vertex
</span><a href="#local-6989586621680816861"><span class="hs-identifier hs-var">key_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816851"><span class="hs-identifier hs-var">ks</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-128"></span><span>                             </span><span class="hs-glyph">|</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816854"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816854"><span class="hs-identifier hs-var">v</span></a></span></span><span class="hs-special">,</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload -&gt; [key]
forall key payload. Node key payload -&gt; [key]
</span><a href="GHC.Data.Graph.Directed.html#node_dependencies"><span class="hs-identifier hs-var hs-var">node_dependencies</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span id="local-6989586621680816851"><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816851"><span class="hs-identifier hs-var">ks</span></a></span></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[(Vertex, Node key payload)]
</span><a href="#local-6989586621680816857"><span class="hs-identifier hs-var">numbered_nodes</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-129"></span><span>                </span><span class="hs-comment">-- We normalize outgoing edges by sorting on node order, so</span><span>
</span><span id="line-130"></span><span>                </span><span class="hs-comment">-- that the result doesn't depend on the order of the edges</span><span>
</span><span id="line-131"></span><span>
</span><span id="line-132"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-133"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-134"></span><span id="local-6989586621680817091"><span id="local-6989586621680817092"><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesOrd"><span class="hs-identifier hs-type">graphFromEdgedVerticesOrd</span></a></span><span>
</span><span id="line-135"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680817092"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-136"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817092"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817091"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>           </span><span class="hs-comment">-- The graph; its ok for the</span><span>
</span><span id="line-137"></span><span>                                        </span><span class="hs-comment">-- out-list to contain keys which aren't</span><span>
</span><span id="line-138"></span><span>                                        </span><span class="hs-comment">-- a vertex key, they are ignored</span><span>
</span><span id="line-139"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817092"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817091"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-140"></span><span id="graphFromEdgedVerticesOrd"><span class="annot"><span class="annottext">graphFromEdgedVerticesOrd :: forall key payload.
Ord key =&gt;
[Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesOrd"><span class="hs-identifier hs-var hs-var">graphFromEdgedVerticesOrd</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
forall key payload.
ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var">graphFromEdgedVertices</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
forall key payload. Ord key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesOrd"><span class="hs-identifier hs-var">reduceNodesIntoVerticesOrd</span></a></span><span>
</span><span id="line-141"></span><span>
</span><span id="line-142"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-143"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-144"></span><span id="local-6989586621680817084"><span id="local-6989586621680817086"><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesUniq"><span class="hs-identifier hs-type">graphFromEdgedVerticesUniq</span></a></span><span>
</span><span id="line-145"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817086"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-146"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817086"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817084"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>           </span><span class="hs-comment">-- The graph; its ok for the</span><span>
</span><span id="line-147"></span><span>                                        </span><span class="hs-comment">-- out-list to contain keys which aren't</span><span>
</span><span id="line-148"></span><span>                                        </span><span class="hs-comment">-- a vertex key, they are ignored</span><span>
</span><span id="line-149"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817086"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817084"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span></span></span><span>
</span><span id="line-150"></span><span id="graphFromEdgedVerticesUniq"><span class="annot"><span class="annottext">graphFromEdgedVerticesUniq :: forall key payload.
Uniquable key =&gt;
[Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVerticesUniq"><span class="hs-identifier hs-var hs-var">graphFromEdgedVerticesUniq</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
forall key payload.
ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var">graphFromEdgedVertices</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
forall key payload. Uniquable key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesUniq"><span class="hs-identifier hs-var">reduceNodesIntoVerticesUniq</span></a></span><span>
</span><span id="line-151"></span><span>
</span><span id="line-152"></span><span class="hs-keyword">type</span><span> </span><span id="ReduceFn"><span class="annot"><a href="GHC.Data.Graph.Directed.html#ReduceFn"><span class="hs-identifier hs-var">ReduceFn</span></a></span></span><span> </span><span id="local-6989586621680816844"><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span></span><span> </span><span id="local-6989586621680816843"><span class="annot"><a href="#local-6989586621680816843"><span class="hs-identifier hs-type">payload</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-153"></span><span>  </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816843"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816843"><span class="hs-identifier hs-type">payload</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span>
</span><span id="line-154"></span><span>    </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Bounds"><span class="hs-identifier hs-type">Bounds</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816843"><span class="hs-identifier hs-type">payload</span></a></span><span>
</span><span id="line-155"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816844"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816843"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-156"></span><span>
</span><span id="line-157"></span><span class="hs-comment">{-
Note [reduceNodesIntoVertices implementations]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reduceNodesIntoVertices is parameterized by the container type.
This is to accommodate key types that don't have an Ord instance
and hence preclude the use of Data.Map. An example of such type
would be Unique, there's no way to implement Ord Unique
deterministically.

For such types, there's a version with a Uniquable constraint.
This leaves us with two versions of every function that depends on
reduceNodesIntoVertices, one with Ord constraint and the other with
Uniquable constraint.
For example: graphFromEdgedVerticesOrd and graphFromEdgedVerticesUniq.

The Uniq version should be a tiny bit more efficient since it uses
Data.IntMap internally.
-}</span><span>
</span><span id="line-175"></span><span id="local-6989586621680817077"><span id="local-6989586621680817078"><span id="local-6989586621680817079"><span class="annot"><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVertices"><span class="hs-identifier hs-type">reduceNodesIntoVertices</span></a></span><span>
</span><span id="line-176"></span><span>  </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680817079"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680817078"><span class="hs-identifier hs-type">m</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-177"></span><span>  </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680817079"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680817078"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-178"></span><span>  </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#ReduceFn"><span class="hs-identifier hs-type">ReduceFn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817079"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817077"><span class="hs-identifier hs-type">payload</span></a></span></span></span></span><span>
</span><span id="line-179"></span><span id="reduceNodesIntoVertices"><span class="annot"><span class="annottext">reduceNodesIntoVertices :: forall key m payload.
([(key, Vertex)] -&gt; m)
-&gt; (key -&gt; m -&gt; Maybe Vertex) -&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVertices"><span class="hs-identifier hs-var hs-var">reduceNodesIntoVertices</span></a></span></span><span> </span><span id="local-6989586621680816839"><span class="annot"><span class="annottext">[(key, Vertex)] -&gt; m
</span><a href="#local-6989586621680816839"><span class="hs-identifier hs-var">fromList</span></a></span></span><span> </span><span id="local-6989586621680816838"><span class="annot"><span class="annottext">key -&gt; m -&gt; Maybe Vertex
</span><a href="#local-6989586621680816838"><span class="hs-identifier hs-var">lookup</span></a></span></span><span> </span><span id="local-6989586621680816837"><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816837"><span class="hs-identifier hs-var">nodes</span></a></span></span><span> </span><span id="local-6989586621680816836"><span class="annot"><span class="annottext">Node key payload -&gt; key
</span><a href="#local-6989586621680816836"><span class="hs-identifier hs-var">key_extractor</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-180"></span><span>  </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621680816835"><span class="hs-identifier hs-var">bounds</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Array Vertex (Node key payload) -&gt; Vertex -&gt; Node key payload
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">(!)</span></a></span><span> </span><span class="annot"><span class="annottext">Array Vertex (Node key payload)
</span><a href="#local-6989586621680816833"><span class="hs-identifier hs-var">vertex_map</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">key -&gt; Maybe Vertex
</span><a href="#local-6989586621680816832"><span class="hs-identifier hs-var">key_vertex</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[(Vertex, Node key payload)]
</span><a href="#local-6989586621680816831"><span class="hs-identifier hs-var">numbered_nodes</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-181"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-182"></span><span>    </span><span id="local-6989586621680816826"><span class="annot"><span class="annottext">max_v :: Vertex
</span><a href="#local-6989586621680816826"><span class="hs-identifier hs-var hs-var">max_v</span></a></span></span><span>           </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Node key payload] -&gt; Vertex
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Vertex
</span><a href="../../base/src/Data.Foldable.html#length"><span class="hs-identifier hs-var">length</span></a></span><span> </span><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816837"><span class="hs-identifier hs-var">nodes</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Vertex -&gt; Vertex
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#-"><span class="hs-glyph hs-var">-</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">1</span></span><span>
</span><span id="line-183"></span><span>    </span><span id="local-6989586621680816835"><span class="annot"><span class="annottext">bounds :: (Vertex, Vertex)
</span><a href="#local-6989586621680816835"><span class="hs-identifier hs-var hs-var">bounds</span></a></span></span><span>          </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">0</span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816826"><span class="hs-identifier hs-var">max_v</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-184"></span><span>
</span><span id="line-185"></span><span>    </span><span class="hs-comment">-- Keep the order intact to make the result depend on input order</span><span>
</span><span id="line-186"></span><span>    </span><span class="hs-comment">-- instead of key order</span><span>
</span><span id="line-187"></span><span>    </span><span id="local-6989586621680816831"><span class="annot"><span class="annottext">numbered_nodes :: [(Vertex, Node key payload)]
</span><a href="#local-6989586621680816831"><span class="hs-identifier hs-var hs-var">numbered_nodes</span></a></span></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Vertex] -&gt; [Node key payload] -&gt; [(Vertex, Node key payload)]
forall a b. [a] -&gt; [b] -&gt; [(a, b)]
</span><a href="../../base/src/GHC.List.html#zip"><span class="hs-identifier hs-var">zip</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">0</span></span><span class="hs-glyph">..</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816837"><span class="hs-identifier hs-var">nodes</span></a></span><span>
</span><span id="line-188"></span><span>    </span><span id="local-6989586621680816833"><span class="annot"><span class="annottext">vertex_map :: Array Vertex (Node key payload)
</span><a href="#local-6989586621680816833"><span class="hs-identifier hs-var hs-var">vertex_map</span></a></span></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex)
-&gt; [(Vertex, Node key payload)] -&gt; Array Vertex (Node key payload)
forall i e. Ix i =&gt; (i, i) -&gt; [(i, e)] -&gt; Array i e
</span><a href="../../base/src/GHC.Arr.html#array"><span class="hs-identifier hs-var">array</span></a></span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621680816835"><span class="hs-identifier hs-var">bounds</span></a></span><span> </span><span class="annot"><span class="annottext">[(Vertex, Node key payload)]
</span><a href="#local-6989586621680816831"><span class="hs-identifier hs-var">numbered_nodes</span></a></span><span>
</span><span id="line-189"></span><span>
</span><span id="line-190"></span><span>    </span><span id="local-6989586621680816820"><span class="annot"><span class="annottext">key_map :: m
</span><a href="#local-6989586621680816820"><span class="hs-identifier hs-var hs-var">key_map</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[(key, Vertex)] -&gt; m
</span><a href="#local-6989586621680816839"><span class="hs-identifier hs-var">fromList</span></a></span><span>
</span><span id="line-191"></span><span>      </span><span class="hs-special">[</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload -&gt; key
</span><a href="#local-6989586621680816836"><span class="hs-identifier hs-var">key_extractor</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816819"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816818"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">|</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816818"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816818"><span class="hs-identifier hs-var">v</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816819"><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816819"><span class="hs-identifier hs-var">node</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[(Vertex, Node key payload)]
</span><a href="#local-6989586621680816831"><span class="hs-identifier hs-var">numbered_nodes</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-192"></span><span>    </span><span id="local-6989586621680816832"><span class="annot"><span class="annottext">key_vertex :: key -&gt; Maybe Vertex
</span><a href="#local-6989586621680816832"><span class="hs-identifier hs-var hs-var">key_vertex</span></a></span></span><span> </span><span id="local-6989586621680816817"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816817"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">key -&gt; m -&gt; Maybe Vertex
</span><a href="#local-6989586621680816838"><span class="hs-identifier hs-var">lookup</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816817"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">m
</span><a href="#local-6989586621680816820"><span class="hs-identifier hs-var">key_map</span></a></span><span>
</span><span id="line-193"></span><span>
</span><span id="line-194"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-195"></span><span id="local-6989586621680817087"><span id="local-6989586621680817088"><span class="annot"><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesOrd"><span class="hs-identifier hs-type">reduceNodesIntoVerticesOrd</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680817088"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#ReduceFn"><span class="hs-identifier hs-type">ReduceFn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817088"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817087"><span class="hs-identifier hs-type">payload</span></a></span></span></span><span>
</span><span id="line-196"></span><span id="reduceNodesIntoVerticesOrd"><span class="annot"><span class="annottext">reduceNodesIntoVerticesOrd :: forall key payload. Ord key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesOrd"><span class="hs-identifier hs-var hs-var">reduceNodesIntoVerticesOrd</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">([(key, Vertex)] -&gt; Map key Vertex)
-&gt; (key -&gt; Map key Vertex -&gt; Maybe Vertex) -&gt; ReduceFn key payload
forall key m payload.
([(key, Vertex)] -&gt; m)
-&gt; (key -&gt; m -&gt; Maybe Vertex) -&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVertices"><span class="hs-identifier hs-var">reduceNodesIntoVertices</span></a></span><span> </span><span class="annot"><span class="annottext">[(key, Vertex)] -&gt; Map key Vertex
forall k a. Ord k =&gt; [(k, a)] -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Internal.html#fromList"><span class="hs-identifier hs-var">Map.fromList</span></a></span><span> </span><span class="annot"><span class="annottext">key -&gt; Map key Vertex -&gt; Maybe Vertex
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Maybe a
</span><a href="../../containers/src/Data.Map.Internal.html#lookup"><span class="hs-identifier hs-var">Map.lookup</span></a></span><span>
</span><span id="line-197"></span><span>
</span><span id="line-198"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-199"></span><span id="local-6989586621680817080"><span id="local-6989586621680817081"><span class="annot"><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesUniq"><span class="hs-identifier hs-type">reduceNodesIntoVerticesUniq</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817081"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#ReduceFn"><span class="hs-identifier hs-type">ReduceFn</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817081"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817080"><span class="hs-identifier hs-type">payload</span></a></span></span></span><span>
</span><span id="line-200"></span><span id="reduceNodesIntoVerticesUniq"><span class="annot"><span class="annottext">reduceNodesIntoVerticesUniq :: forall key payload. Uniquable key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesUniq"><span class="hs-identifier hs-var hs-var">reduceNodesIntoVerticesUniq</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">([(key, Vertex)] -&gt; UniqFM key Vertex)
-&gt; (key -&gt; UniqFM key Vertex -&gt; Maybe Vertex)
-&gt; ReduceFn key payload
forall key m payload.
([(key, Vertex)] -&gt; m)
-&gt; (key -&gt; m -&gt; Maybe Vertex) -&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVertices"><span class="hs-identifier hs-var">reduceNodesIntoVertices</span></a></span><span> </span><span class="annot"><span class="annottext">[(key, Vertex)] -&gt; UniqFM key Vertex
forall key elt. Uniquable key =&gt; [(key, elt)] -&gt; UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#listToUFM"><span class="hs-identifier hs-var">listToUFM</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(UniqFM key Vertex -&gt; key -&gt; Maybe Vertex)
-&gt; key -&gt; UniqFM key Vertex -&gt; Maybe Vertex
forall a b c. (a -&gt; b -&gt; c) -&gt; b -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#flip"><span class="hs-identifier hs-var">flip</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Vertex -&gt; key -&gt; Maybe Vertex
forall key elt. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; Maybe elt
</span><a href="GHC.Types.Unique.FM.html#lookupUFM"><span class="hs-identifier hs-var">lookupUFM</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-201"></span><span>
</span><span id="line-202"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      SCC
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-209"></span><span>
</span><span id="line-210"></span><span class="hs-keyword">type</span><span> </span><span id="WorkItem"><span class="annot"><a href="GHC.Data.Graph.Directed.html#WorkItem"><span class="hs-identifier hs-var">WorkItem</span></a></span></span><span> </span><span id="local-6989586621680816805"><span class="annot"><a href="#local-6989586621680816805"><span class="hs-identifier hs-type">key</span></a></span></span><span> </span><span id="local-6989586621680816804"><span class="annot"><a href="#local-6989586621680816804"><span class="hs-identifier hs-type">payload</span></a></span></span><span>
</span><span id="line-211"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816805"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816804"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">,</span><span>  </span><span class="hs-comment">-- Tip of the path</span><span>
</span><span id="line-212"></span><span>     </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816804"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span>         </span><span class="hs-comment">-- Rest of the path;</span><span>
</span><span id="line-213"></span><span>                        </span><span class="hs-comment">--  [a,b,c] means c depends on b, b depends on a</span><span>
</span><span id="line-214"></span><span>
</span><span id="line-215"></span><span class="hs-comment">-- | Find a reasonably short cycle a-&gt;b-&gt;c-&gt;a, in a strongly</span><span>
</span><span id="line-216"></span><span class="hs-comment">-- connected component.  The input nodes are presumed to be</span><span>
</span><span id="line-217"></span><span class="hs-comment">-- a SCC, so you can start anywhere.</span><span>
</span><span id="line-218"></span><span class="annot"><a href="GHC.Data.Graph.Directed.html#findCycle"><span class="hs-identifier hs-type">findCycle</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-keyword">forall</span><span> </span><span id="local-6989586621680817048"><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span></span><span> </span><span id="local-6989586621680817049"><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span></span><span class="hs-operator">.</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-219"></span><span>          </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>     </span><span class="hs-comment">-- The nodes.  The dependencies can</span><span>
</span><span id="line-220"></span><span>                                    </span><span class="hs-comment">-- contain extra keys, which are ignored</span><span>
</span><span id="line-221"></span><span>          </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>        </span><span class="hs-comment">-- A cycle, starting with node</span><span>
</span><span id="line-222"></span><span>                                    </span><span class="hs-comment">-- so each depends on the next</span><span>
</span><span id="line-223"></span><span id="findCycle"><span class="annot"><span class="annottext">findCycle :: forall payload key.
Ord key =&gt;
[Node key payload] -&gt; Maybe [payload]
</span><a href="GHC.Data.Graph.Directed.html#findCycle"><span class="hs-identifier hs-var hs-var">findCycle</span></a></span></span><span> </span><span id="local-6989586621680816792"><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816792"><span class="hs-identifier hs-var">graph</span></a></span></span><span>
</span><span id="line-224"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
forall a. Set a
</span><a href="../../containers/src/Data.Set.Internal.html#empty"><span class="hs-identifier hs-var">Set.empty</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[key] -&gt; [payload] -&gt; [WorkItem key payload]
</span><a href="#local-6989586621680816789"><span class="hs-identifier hs-var">new_work</span></a></span><span> </span><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816788"><span class="hs-identifier hs-var">root_deps</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-225"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-226"></span><span>    </span><span class="annot"><a href="#local-6989586621680816787"><span class="hs-identifier hs-type">env</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Map.Internal.html#Map"><span class="hs-identifier hs-type">Map.Map</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-227"></span><span>    </span><span id="local-6989586621680816787"><span class="annot"><span class="annottext">env :: Map key (Node key payload)
</span><a href="#local-6989586621680816787"><span class="hs-identifier hs-var hs-var">env</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[(key, Node key payload)] -&gt; Map key (Node key payload)
forall k a. Ord k =&gt; [(k, a)] -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Internal.html#fromList"><span class="hs-identifier hs-var">Map.fromList</span></a></span><span> </span><span class="hs-special">[</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload -&gt; key
forall key payload. Node key payload -&gt; key
</span><a href="GHC.Data.Graph.Directed.html#node_key"><span class="hs-identifier hs-var hs-var">node_key</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816786"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816786"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">|</span><span> </span><span id="local-6989586621680816786"><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816786"><span class="hs-identifier hs-var">node</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816792"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-228"></span><span>
</span><span id="line-229"></span><span>    </span><span class="hs-comment">-- Find the node with fewest dependencies among the SCC modules</span><span>
</span><span id="line-230"></span><span>    </span><span class="hs-comment">-- This is just a heuristic to find some plausible root module</span><span>
</span><span id="line-231"></span><span>    </span><span class="annot"><a href="#local-6989586621680816785"><span class="hs-identifier hs-type">root</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span>
</span><span id="line-232"></span><span>    </span><span id="local-6989586621680816785"><span class="annot"><span class="annottext">root :: Node key payload
</span><a href="#local-6989586621680816785"><span class="hs-identifier hs-var hs-var">root</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Node key payload, Vertex) -&gt; Node key payload
forall a b. (a, b) -&gt; a
</span><a href="../../base/src/Data.Tuple.html#fst"><span class="hs-identifier hs-var">fst</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">((Node key payload, Vertex) -&gt; Vertex)
-&gt; [(Node key payload, Vertex)] -&gt; (Node key payload, Vertex)
forall b a. Ord b =&gt; (a -&gt; b) -&gt; [a] -&gt; a
</span><a href="GHC.Utils.Misc.html#minWith"><span class="hs-identifier hs-var">minWith</span></a></span><span> </span><span class="annot"><span class="annottext">(Node key payload, Vertex) -&gt; Vertex
forall a b. (a, b) -&gt; b
</span><a href="../../base/src/Data.Tuple.html#snd"><span class="hs-identifier hs-var">snd</span></a></span><span> </span><span class="hs-special">[</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816784"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">(key -&gt; Bool) -&gt; [key] -&gt; Vertex
forall a. (a -&gt; Bool) -&gt; [a] -&gt; Vertex
</span><a href="GHC.Utils.Misc.html#count"><span class="hs-identifier hs-var">count</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Map key (Node key payload) -&gt; Bool
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Bool
</span><a href="../../containers/src/Data.Map.Internal.html#member"><span class="hs-operator hs-var">`Map.member`</span></a></span><span> </span><span class="annot"><span class="annottext">Map key (Node key payload)
</span><a href="#local-6989586621680816787"><span class="hs-identifier hs-var">env</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-233"></span><span>                                           </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload -&gt; [key]
forall key payload. Node key payload -&gt; [key]
</span><a href="GHC.Data.Graph.Directed.html#node_dependencies"><span class="hs-identifier hs-var hs-var">node_dependencies</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816784"><span class="hs-identifier hs-var">node</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-234"></span><span>                            </span><span class="hs-glyph">|</span><span> </span><span id="local-6989586621680816784"><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816784"><span class="hs-identifier hs-var">node</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[Node key payload]
</span><a href="#local-6989586621680816792"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-235"></span><span>    </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#DigraphNode"><span class="hs-identifier hs-type">DigraphNode</span></a></span><span> </span><span id="local-6989586621680816782"><span class="annot"><span class="annottext">payload
</span><a href="#local-6989586621680816782"><span class="hs-identifier hs-var">root_payload</span></a></span></span><span> </span><span id="local-6989586621680816781"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816781"><span class="hs-identifier hs-var">root_key</span></a></span></span><span> </span><span id="local-6989586621680816788"><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816788"><span class="hs-identifier hs-var">root_deps</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816785"><span class="hs-identifier hs-var">root</span></a></span><span>
</span><span id="line-236"></span><span>
</span><span id="line-237"></span><span>
</span><span id="line-238"></span><span>    </span><span class="hs-comment">-- 'go' implements Dijkstra's algorithm, more or less</span><span>
</span><span id="line-239"></span><span>    </span><span class="annot"><a href="#local-6989586621680816791"><span class="hs-identifier hs-type">go</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Set.Internal.html#Set"><span class="hs-identifier hs-type">Set.Set</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span>   </span><span class="hs-comment">-- Visited</span><span>
</span><span id="line-240"></span><span>       </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#WorkItem"><span class="hs-identifier hs-type">WorkItem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>        </span><span class="hs-comment">-- Work list, items length n</span><span>
</span><span id="line-241"></span><span>       </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#WorkItem"><span class="hs-identifier hs-type">WorkItem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>        </span><span class="hs-comment">-- Work list, items length n+1</span><span>
</span><span id="line-242"></span><span>       </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>               </span><span class="hs-comment">-- Returned cycle</span><span>
</span><span id="line-243"></span><span>       </span><span class="hs-comment">-- Invariant: in a call (go visited ps qs),</span><span>
</span><span id="line-244"></span><span>       </span><span class="hs-comment">--            visited = union (map tail (ps ++ qs))</span><span>
</span><span id="line-245"></span><span>
</span><span id="line-246"></span><span>    </span><span id="local-6989586621680816791"><span class="annot"><span class="annottext">go :: Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var hs-var">go</span></a></span></span><span> </span><span class="annot"><span class="annottext">Set key
</span><span class="hs-identifier">_</span></span><span>       </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe [payload]
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span>  </span><span class="hs-comment">-- No cycles</span><span>
</span><span id="line-247"></span><span>    </span><span class="annot"><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span id="local-6989586621680816780"><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816780"><span class="hs-identifier hs-var">visited</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span id="local-6989586621680816779"><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816779"><span class="hs-identifier hs-var">qs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816780"><span class="hs-identifier hs-var">visited</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816779"><span class="hs-identifier hs-var">qs</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-248"></span><span>    </span><span class="annot"><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span id="local-6989586621680816778"><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816778"><span class="hs-identifier hs-var">visited</span></a></span></span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#DigraphNode"><span class="hs-identifier hs-type">DigraphNode</span></a></span><span> </span><span id="local-6989586621680816777"><span class="annot"><span class="annottext">payload
</span><a href="#local-6989586621680816777"><span class="hs-identifier hs-var">payload</span></a></span></span><span> </span><span id="local-6989586621680816776"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816776"><span class="hs-identifier hs-var">key</span></a></span></span><span> </span><span id="local-6989586621680816775"><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816775"><span class="hs-identifier hs-var">deps</span></a></span></span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816774"><span class="annot"><span class="annottext">[payload]
</span><a href="#local-6989586621680816774"><span class="hs-identifier hs-var">path</span></a></span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span> </span><span id="local-6989586621680816773"><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816773"><span class="hs-identifier hs-var">ps</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621680816772"><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816772"><span class="hs-identifier hs-var">qs</span></a></span></span><span>
</span><span id="line-249"></span><span>       </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816776"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="annot"><span class="annottext">key -&gt; key -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816781"><span class="hs-identifier hs-var">root_key</span></a></span><span>           </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[payload] -&gt; Maybe [payload]
forall a. a -&gt; Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-var">Just</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">payload
</span><a href="#local-6989586621680816782"><span class="hs-identifier hs-var">root_payload</span></a></span><span> </span><span class="annot"><span class="annottext">payload -&gt; [payload] -&gt; [payload]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">[payload] -&gt; [payload]
forall a. [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#reverse"><span class="hs-identifier hs-var">reverse</span></a></span><span> </span><span class="annot"><span class="annottext">[payload]
</span><a href="#local-6989586621680816774"><span class="hs-identifier hs-var">path</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-250"></span><span>       </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816776"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="annot"><span class="annottext">key -&gt; Set key -&gt; Bool
forall a. Ord a =&gt; a -&gt; Set a -&gt; Bool
</span><a href="../../containers/src/Data.Set.Internal.html#member"><span class="hs-operator hs-var">`Set.member`</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816778"><span class="hs-identifier hs-var">visited</span></a></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816778"><span class="hs-identifier hs-var">visited</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816773"><span class="hs-identifier hs-var">ps</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816772"><span class="hs-identifier hs-var">qs</span></a></span><span>
</span><span id="line-251"></span><span>       </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816776"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="annot"><span class="annottext">key -&gt; Map key (Node key payload) -&gt; Bool
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Bool
</span><a href="../../containers/src/Data.Map.Internal.html#notMember"><span class="hs-operator hs-var">`Map.notMember`</span></a></span><span> </span><span class="annot"><span class="annottext">Map key (Node key payload)
</span><a href="#local-6989586621680816787"><span class="hs-identifier hs-var">env</span></a></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816778"><span class="hs-identifier hs-var">visited</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816773"><span class="hs-identifier hs-var">ps</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816772"><span class="hs-identifier hs-var">qs</span></a></span><span>
</span><span id="line-252"></span><span>       </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>                 </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Set key
-&gt; [WorkItem key payload]
-&gt; [WorkItem key payload]
-&gt; Maybe [payload]
</span><a href="#local-6989586621680816791"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Set key -&gt; Set key
forall a. Ord a =&gt; a -&gt; Set a -&gt; Set a
</span><a href="../../containers/src/Data.Set.Internal.html#insert"><span class="hs-identifier hs-var">Set.insert</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816776"><span class="hs-identifier hs-var">key</span></a></span><span> </span><span class="annot"><span class="annottext">Set key
</span><a href="#local-6989586621680816778"><span class="hs-identifier hs-var">visited</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-253"></span><span>                                        </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816773"><span class="hs-identifier hs-var">ps</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816767"><span class="hs-identifier hs-var">new_qs</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
-&gt; [WorkItem key payload] -&gt; [WorkItem key payload]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[WorkItem key payload]
</span><a href="#local-6989586621680816772"><span class="hs-identifier hs-var">qs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-254"></span><span>       </span><span class="hs-keyword">where</span><span>
</span><span id="line-255"></span><span>         </span><span id="local-6989586621680816767"><span class="annot"><span class="annottext">new_qs :: [WorkItem key payload]
</span><a href="#local-6989586621680816767"><span class="hs-identifier hs-var hs-var">new_qs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[key] -&gt; [payload] -&gt; [WorkItem key payload]
</span><a href="#local-6989586621680816789"><span class="hs-identifier hs-var">new_work</span></a></span><span> </span><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816775"><span class="hs-identifier hs-var">deps</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">payload
</span><a href="#local-6989586621680816777"><span class="hs-identifier hs-var">payload</span></a></span><span> </span><span class="annot"><span class="annottext">payload -&gt; [payload] -&gt; [payload]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">[payload]
</span><a href="#local-6989586621680816774"><span class="hs-identifier hs-var">path</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-256"></span><span>
</span><span id="line-257"></span><span>    </span><span class="annot"><a href="#local-6989586621680816789"><span class="hs-identifier hs-type">new_work</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#WorkItem"><span class="hs-identifier hs-type">WorkItem</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817049"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817048"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-258"></span><span>    </span><span id="local-6989586621680816789"><span class="annot"><span class="annottext">new_work :: [key] -&gt; [payload] -&gt; [WorkItem key payload]
</span><a href="#local-6989586621680816789"><span class="hs-identifier hs-var hs-var">new_work</span></a></span></span><span> </span><span id="local-6989586621680816766"><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816766"><span class="hs-identifier hs-var">deps</span></a></span></span><span> </span><span id="local-6989586621680816765"><span class="annot"><span class="annottext">[payload]
</span><a href="#local-6989586621680816765"><span class="hs-identifier hs-var">path</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816764"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[payload]
</span><a href="#local-6989586621680816765"><span class="hs-identifier hs-var">path</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680816764"><span class="annot"><span class="annottext">Node key payload
</span><a href="#local-6989586621680816764"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(key -&gt; Maybe (Node key payload))
-&gt; [key] -&gt; [Maybe (Node key payload)]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Map key (Node key payload) -&gt; Maybe (Node key payload)
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Maybe a
</span><a href="../../containers/src/Data.Map.Internal.html#lookup"><span class="hs-operator hs-var">`Map.lookup`</span></a></span><span> </span><span class="annot"><span class="annottext">Map key (Node key payload)
</span><a href="#local-6989586621680816787"><span class="hs-identifier hs-var">env</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816766"><span class="hs-identifier hs-var">deps</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-259"></span><span>
</span><span id="line-260"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      Strongly Connected Component wrappers for Graph
*                                                                      *
************************************************************************

Note: the components are returned topologically sorted: later components
depend on earlier ones, but not vice versa i.e. later components only have
edges going from them to earlier ones.
-}</span><span>
</span><span id="line-271"></span><span>
</span><span id="line-272"></span><span class="hs-comment">{-
Note [Deterministic SCC]
~~~~~~~~~~~~~~~~~~~~~~~~
stronglyConnCompFromEdgedVerticesUniq,
stronglyConnCompFromEdgedVerticesUniqR,
stronglyConnCompFromEdgedVerticesOrd and
stronglyConnCompFromEdgedVerticesOrdR
provide a following guarantee:
Given a deterministically ordered list of nodes it returns a deterministically
ordered list of strongly connected components, where the list of vertices
in an SCC is also deterministically ordered.
Note that the order of edges doesn't need to be deterministic for this to work.
We use the order of nodes to normalize the order of edges.
-}</span><span>
</span><span id="line-286"></span><span>
</span><span id="line-287"></span><span id="local-6989586621680817025"><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompG"><span class="hs-identifier hs-type">stronglyConnCompG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817025"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817025"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-288"></span><span id="stronglyConnCompG"><span class="annot"><span class="annottext">stronglyConnCompG :: forall node. Graph node -&gt; [SCC node]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompG"><span class="hs-identifier hs-var hs-var">stronglyConnCompG</span></a></span></span><span> </span><span id="local-6989586621680816763"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816763"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph node -&gt; Forest Vertex -&gt; [SCC node]
forall node. Graph node -&gt; Forest Vertex -&gt; [SCC node]
</span><a href="GHC.Data.Graph.Directed.html#decodeSccs"><span class="hs-identifier hs-var">decodeSccs</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816763"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">Forest Vertex
</span><a href="#local-6989586621680816761"><span class="hs-identifier hs-var">forest</span></a></span><span>
</span><span id="line-289"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816761"><span class="annot"><span class="annottext">forest :: Forest Vertex
</span><a href="#local-6989586621680816761"><span class="hs-identifier hs-var hs-var">forest</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-pragma">{-# SCC</span><span> </span><span class="hs-pragma">&quot;Digraph.scc&quot;</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; Forest Vertex
</span><a href="../../containers/src/Data.Graph.html#scc"><span class="hs-identifier hs-var">scc</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816763"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-290"></span><span>
</span><span id="line-291"></span><span id="local-6989586621680817021"><span class="annot"><a href="GHC.Data.Graph.Directed.html#decodeSccs"><span class="hs-identifier hs-type">decodeSccs</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817021"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#Forest"><span class="hs-identifier hs-type">Forest</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817021"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-292"></span><span id="decodeSccs"><span class="annot"><span class="annottext">decodeSccs :: forall node. Graph node -&gt; Forest Vertex -&gt; [SCC node]
</span><a href="GHC.Data.Graph.Directed.html#decodeSccs"><span class="hs-identifier hs-var hs-var">decodeSccs</span></a></span></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">{</span><span> </span><span class="annot"><span class="annottext">gr_int_graph :: forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var">gr_int_graph</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621680816759"><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816759"><span class="hs-identifier hs-var">graph</span></a></span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">gr_vertex_to_node :: forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621680816758"><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816758"><span class="hs-identifier hs-var">vertex_fn</span></a></span></span><span> </span><span class="hs-special">}</span><span> </span><span id="local-6989586621680816757"><span class="annot"><span class="annottext">Forest Vertex
</span><a href="#local-6989586621680816757"><span class="hs-identifier hs-var">forest</span></a></span></span><span>
</span><span id="line-293"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Tree Vertex -&gt; SCC node) -&gt; Forest Vertex -&gt; [SCC node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex -&gt; SCC node
</span><a href="#local-6989586621680816756"><span class="hs-identifier hs-var">decode</span></a></span><span> </span><span class="annot"><span class="annottext">Forest Vertex
</span><a href="#local-6989586621680816757"><span class="hs-identifier hs-var">forest</span></a></span><span>
</span><span id="line-294"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-295"></span><span>    </span><span id="local-6989586621680816756"><span class="annot"><span class="annottext">decode :: Tree Vertex -&gt; SCC node
</span><a href="#local-6989586621680816756"><span class="hs-identifier hs-var hs-var">decode</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621680816754"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816754"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Bool
</span><a href="#local-6989586621680816753"><span class="hs-identifier hs-var">mentions_itself</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816754"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[node] -&gt; SCC node
forall vertex. [vertex] -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#CyclicSCC"><span class="hs-identifier hs-var">CyclicSCC</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816758"><span class="hs-identifier hs-var">vertex_fn</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816754"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-296"></span><span>                       </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">node -&gt; SCC node
forall vertex. vertex -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#AcyclicSCC"><span class="hs-identifier hs-var">AcyclicSCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816758"><span class="hs-identifier hs-var">vertex_fn</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816754"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-297"></span><span>    </span><span class="annot"><a href="#local-6989586621680816756"><span class="hs-identifier hs-var">decode</span></a></span><span> </span><span id="local-6989586621680816750"><span class="annot"><span class="annottext">Tree Vertex
</span><a href="#local-6989586621680816750"><span class="hs-identifier hs-var">other</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[node] -&gt; SCC node
forall vertex. [vertex] -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#CyclicSCC"><span class="hs-identifier hs-var">CyclicSCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree Vertex -&gt; [node] -&gt; [node]
</span><a href="#local-6989586621680816749"><span class="hs-identifier hs-var">dec</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex
</span><a href="#local-6989586621680816750"><span class="hs-identifier hs-var">other</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-298"></span><span>      </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816749"><span class="annot"><span class="annottext">dec :: Tree Vertex -&gt; [node] -&gt; [node]
</span><a href="#local-6989586621680816749"><span class="hs-identifier hs-var hs-var">dec</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621680816747"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816747"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span id="local-6989586621680816746"><span class="annot"><span class="annottext">Forest Vertex
</span><a href="#local-6989586621680816746"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621680816745"><span class="annot"><span class="annottext">[node]
</span><a href="#local-6989586621680816745"><span class="hs-identifier hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816758"><span class="hs-identifier hs-var">vertex_fn</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816747"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="annot"><span class="annottext">node -&gt; [node] -&gt; [node]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">(Tree Vertex -&gt; [node] -&gt; [node])
-&gt; [node] -&gt; Forest Vertex -&gt; [node]
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var">foldr</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex -&gt; [node] -&gt; [node]
</span><a href="#local-6989586621680816749"><span class="hs-identifier hs-var">dec</span></a></span><span> </span><span class="annot"><span class="annottext">[node]
</span><a href="#local-6989586621680816745"><span class="hs-identifier hs-var">vs</span></a></span><span> </span><span class="annot"><span class="annottext">Forest Vertex
</span><a href="#local-6989586621680816746"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-299"></span><span>    </span><span id="local-6989586621680816753"><span class="annot"><span class="annottext">mentions_itself :: Vertex -&gt; Bool
</span><a href="#local-6989586621680816753"><span class="hs-identifier hs-var hs-var">mentions_itself</span></a></span></span><span> </span><span id="local-6989586621680816739"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816739"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816739"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; [Vertex] -&gt; Bool
forall (t :: * -&gt; *) a. (Foldable t, Eq a) =&gt; a -&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#elem"><span class="hs-operator hs-var">`elem`</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816759"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; Vertex -&gt; [Vertex]
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">!</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816739"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-300"></span><span>
</span><span id="line-301"></span><span>
</span><span id="line-302"></span><span class="hs-comment">-- The following two versions are provided for backwards compatibility:</span><span>
</span><span id="line-303"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-304"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-305"></span><span id="local-6989586621680817013"><span id="local-6989586621680817014"><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrd"><span class="hs-identifier hs-type">stronglyConnCompFromEdgedVerticesOrd</span></a></span><span>
</span><span id="line-306"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680817014"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-307"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817014"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817013"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-308"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817013"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span></span></span><span>
</span><span id="line-309"></span><span id="stronglyConnCompFromEdgedVerticesOrd"><span class="annot"><span class="annottext">stronglyConnCompFromEdgedVerticesOrd :: forall key payload. Ord key =&gt; [Node key payload] -&gt; [SCC payload]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrd"><span class="hs-identifier hs-var hs-var">stronglyConnCompFromEdgedVerticesOrd</span></a></span></span><span>
</span><span id="line-310"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(SCC (Node key payload) -&gt; SCC payload)
-&gt; [SCC (Node key payload)] -&gt; [SCC payload]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Node key payload -&gt; payload)
-&gt; SCC (Node key payload) -&gt; SCC payload
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-identifier hs-var">fmap</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload -&gt; payload
forall key payload. Node key payload -&gt; payload
</span><a href="GHC.Data.Graph.Directed.html#node_payload"><span class="hs-identifier hs-var hs-var">node_payload</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([SCC (Node key payload)] -&gt; [SCC payload])
-&gt; ([Node key payload] -&gt; [SCC (Node key payload)])
-&gt; [Node key payload]
-&gt; [SCC payload]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[Node key payload] -&gt; [SCC (Node key payload)]
forall key payload.
Ord key =&gt;
[Node key payload] -&gt; [SCC (Node key payload)]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrdR"><span class="hs-identifier hs-var">stronglyConnCompFromEdgedVerticesOrdR</span></a></span><span>
</span><span id="line-311"></span><span>
</span><span id="line-312"></span><span class="hs-comment">-- The following two versions are provided for backwards compatibility:</span><span>
</span><span id="line-313"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-314"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-315"></span><span id="local-6989586621680817004"><span id="local-6989586621680817005"><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniq"><span class="hs-identifier hs-type">stronglyConnCompFromEdgedVerticesUniq</span></a></span><span>
</span><span id="line-316"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817005"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-317"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817005"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817004"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-318"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817004"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span></span></span><span>
</span><span id="line-319"></span><span id="stronglyConnCompFromEdgedVerticesUniq"><span class="annot"><span class="annottext">stronglyConnCompFromEdgedVerticesUniq :: forall key payload.
Uniquable key =&gt;
[Node key payload] -&gt; [SCC payload]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniq"><span class="hs-identifier hs-var hs-var">stronglyConnCompFromEdgedVerticesUniq</span></a></span></span><span>
</span><span id="line-320"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(SCC (Node key payload) -&gt; SCC payload)
-&gt; [SCC (Node key payload)] -&gt; [SCC payload]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Node key payload -&gt; payload)
-&gt; SCC (Node key payload) -&gt; SCC payload
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-identifier hs-var">fmap</span></a></span><span> </span><span class="annot"><span class="annottext">Node key payload -&gt; payload
forall key payload. Node key payload -&gt; payload
</span><a href="GHC.Data.Graph.Directed.html#node_payload"><span class="hs-identifier hs-var hs-var">node_payload</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([SCC (Node key payload)] -&gt; [SCC payload])
-&gt; ([Node key payload] -&gt; [SCC (Node key payload)])
-&gt; [Node key payload]
-&gt; [SCC payload]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[Node key payload] -&gt; [SCC (Node key payload)]
forall key payload.
Uniquable key =&gt;
[Node key payload] -&gt; [SCC (Node key payload)]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniqR"><span class="hs-identifier hs-var">stronglyConnCompFromEdgedVerticesUniqR</span></a></span><span>
</span><span id="line-321"></span><span>
</span><span id="line-322"></span><span class="hs-comment">-- The &quot;R&quot; interface is used when you expect to apply SCC to</span><span>
</span><span id="line-323"></span><span class="hs-comment">-- (some of) the result of SCC, so you don't want to lose the dependency info</span><span>
</span><span id="line-324"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-325"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-326"></span><span id="local-6989586621680817006"><span id="local-6989586621680817007"><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrdR"><span class="hs-identifier hs-type">stronglyConnCompFromEdgedVerticesOrdR</span></a></span><span>
</span><span id="line-327"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621680817007"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-328"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817007"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817006"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-329"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817007"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817006"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span></span></span><span>
</span><span id="line-330"></span><span id="stronglyConnCompFromEdgedVerticesOrdR"><span class="annot"><span class="annottext">stronglyConnCompFromEdgedVerticesOrdR :: forall key payload.
Ord key =&gt;
[Node key payload] -&gt; [SCC (Node key payload)]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesOrdR"><span class="hs-identifier hs-var hs-var">stronglyConnCompFromEdgedVerticesOrdR</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-331"></span><span>  </span><span class="annot"><span class="annottext">Graph (Node key payload) -&gt; [SCC (Node key payload)]
forall node. Graph node -&gt; [SCC node]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompG"><span class="hs-identifier hs-var">stronglyConnCompG</span></a></span><span> </span><span class="annot"><span class="annottext">(Graph (Node key payload) -&gt; [SCC (Node key payload)])
-&gt; ([Node key payload] -&gt; Graph (Node key payload))
-&gt; [Node key payload]
-&gt; [SCC (Node key payload)]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
forall key payload.
ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var">graphFromEdgedVertices</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
forall key payload. Ord key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesOrd"><span class="hs-identifier hs-var">reduceNodesIntoVerticesOrd</span></a></span><span>
</span><span id="line-332"></span><span>
</span><span id="line-333"></span><span class="hs-comment">-- The &quot;R&quot; interface is used when you expect to apply SCC to</span><span>
</span><span id="line-334"></span><span class="hs-comment">-- (some of) the result of SCC, so you don't want to lose the dependency info</span><span>
</span><span id="line-335"></span><span class="hs-comment">-- See Note [Deterministic SCC]</span><span>
</span><span id="line-336"></span><span class="hs-comment">-- See Note [reduceNodesIntoVertices implementations]</span><span>
</span><span id="line-337"></span><span id="local-6989586621680817000"><span id="local-6989586621680817001"><span class="annot"><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniqR"><span class="hs-identifier hs-type">stronglyConnCompFromEdgedVerticesUniqR</span></a></span><span>
</span><span id="line-338"></span><span>        </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817001"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-339"></span><span>        </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817001"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817000"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-340"></span><span>        </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817001"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680817000"><span class="hs-identifier hs-type">payload</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span></span></span><span>
</span><span id="line-341"></span><span id="stronglyConnCompFromEdgedVerticesUniqR"><span class="annot"><span class="annottext">stronglyConnCompFromEdgedVerticesUniqR :: forall key payload.
Uniquable key =&gt;
[Node key payload] -&gt; [SCC (Node key payload)]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompFromEdgedVerticesUniqR"><span class="hs-identifier hs-var hs-var">stronglyConnCompFromEdgedVerticesUniqR</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-342"></span><span>  </span><span class="annot"><span class="annottext">Graph (Node key payload) -&gt; [SCC (Node key payload)]
forall node. Graph node -&gt; [SCC node]
</span><a href="GHC.Data.Graph.Directed.html#stronglyConnCompG"><span class="hs-identifier hs-var">stronglyConnCompG</span></a></span><span> </span><span class="annot"><span class="annottext">(Graph (Node key payload) -&gt; [SCC (Node key payload)])
-&gt; ([Node key payload] -&gt; Graph (Node key payload))
-&gt; [Node key payload]
-&gt; [SCC (Node key payload)]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
forall key payload.
ReduceFn key payload
-&gt; [Node key payload] -&gt; Graph (Node key payload)
</span><a href="GHC.Data.Graph.Directed.html#graphFromEdgedVertices"><span class="hs-identifier hs-var">graphFromEdgedVertices</span></a></span><span> </span><span class="annot"><span class="annottext">ReduceFn key payload
forall key payload. Uniquable key =&gt; ReduceFn key payload
</span><a href="GHC.Data.Graph.Directed.html#reduceNodesIntoVerticesUniq"><span class="hs-identifier hs-var">reduceNodesIntoVerticesUniq</span></a></span><span>
</span><span id="line-343"></span><span>
</span><span id="line-344"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      Misc wrappers for Graph
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-351"></span><span>
</span><span id="line-352"></span><span id="local-6989586621680816995"><span class="annot"><a href="GHC.Data.Graph.Directed.html#topologicalSortG"><span class="hs-identifier hs-type">topologicalSortG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816995"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816995"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-353"></span><span id="topologicalSortG"><span class="annot"><span class="annottext">topologicalSortG :: forall node. Graph node -&gt; [node]
</span><a href="GHC.Data.Graph.Directed.html#topologicalSortG"><span class="hs-identifier hs-var hs-var">topologicalSortG</span></a></span></span><span> </span><span id="local-6989586621680816726"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816726"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; node) -&gt; [Vertex] -&gt; [node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816726"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816725"><span class="hs-identifier hs-var">result</span></a></span><span>
</span><span id="line-354"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816725"><span class="annot"><span class="annottext">result :: [Vertex]
</span><a href="#local-6989586621680816725"><span class="hs-identifier hs-var hs-var">result</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-pragma">{-# SCC</span><span> </span><span class="hs-pragma">&quot;Digraph.topSort&quot;</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; [Vertex]
</span><a href="../../containers/src/Data.Graph.html#topSort"><span class="hs-identifier hs-var">topSort</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816726"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-355"></span><span>
</span><span id="line-356"></span><span id="local-6989586621680816993"><span class="annot"><a href="GHC.Data.Graph.Directed.html#reachableG"><span class="hs-identifier hs-type">reachableG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816993"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680816993"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816993"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-357"></span><span id="reachableG"><span class="annot"><span class="annottext">reachableG :: forall node. Graph node -&gt; node -&gt; [node]
</span><a href="GHC.Data.Graph.Directed.html#reachableG"><span class="hs-identifier hs-var hs-var">reachableG</span></a></span></span><span> </span><span id="local-6989586621680816723"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816723"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680816722"><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816722"><span class="hs-identifier hs-var">from</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; node) -&gt; [Vertex] -&gt; [node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816723"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816721"><span class="hs-identifier hs-var">result</span></a></span><span>
</span><span id="line-358"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816718"><span class="annot"><span class="annottext">from_vertex :: Vertex
</span><a href="#local-6989586621680816718"><span class="hs-identifier hs-var hs-var">from_vertex</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; Maybe Vertex -&gt; Vertex
forall a. HasCallStack =&gt; [Char] -&gt; Maybe a -&gt; a
</span><a href="GHC.Data.Maybe.html#expectJust"><span class="hs-identifier hs-var">expectJust</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;reachableG&quot;</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; node -&gt; Maybe Vertex
forall node. Graph node -&gt; node -&gt; Maybe Vertex
</span><a href="GHC.Data.Graph.Directed.html#gr_node_to_vertex"><span class="hs-identifier hs-var hs-var">gr_node_to_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816723"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816722"><span class="hs-identifier hs-var">from</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-359"></span><span>        </span><span id="local-6989586621680816721"><span class="annot"><span class="annottext">result :: [Vertex]
</span><a href="#local-6989586621680816721"><span class="hs-identifier hs-var hs-var">result</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-pragma">{-# SCC</span><span> </span><span class="hs-pragma">&quot;Digraph.reachable&quot;</span><span> </span><span class="hs-pragma">#-}</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; [Vertex] -&gt; [Vertex]
</span><a href="GHC.Data.Graph.Directed.html#reachable"><span class="hs-identifier hs-var">reachable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816723"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816718"><span class="hs-identifier hs-var">from_vertex</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-360"></span><span>
</span><span id="line-361"></span><span class="hs-comment">-- | Given a list of roots return all reachable nodes.</span><span>
</span><span id="line-362"></span><span id="local-6989586621680816990"><span class="annot"><a href="GHC.Data.Graph.Directed.html#reachablesG"><span class="hs-identifier hs-type">reachablesG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816990"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816990"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816990"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-363"></span><span id="reachablesG"><span class="annot"><span class="annottext">reachablesG :: forall node. Graph node -&gt; [node] -&gt; [node]
</span><a href="GHC.Data.Graph.Directed.html#reachablesG"><span class="hs-identifier hs-var hs-var">reachablesG</span></a></span></span><span> </span><span id="local-6989586621680816716"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816716"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680816715"><span class="annot"><span class="annottext">[node]
</span><a href="#local-6989586621680816715"><span class="hs-identifier hs-var">froms</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; node) -&gt; [Vertex] -&gt; [node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816716"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816714"><span class="hs-identifier hs-var">result</span></a></span><span>
</span><span id="line-364"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816714"><span class="annot"><span class="annottext">result :: [Vertex]
</span><a href="#local-6989586621680816714"><span class="hs-identifier hs-var hs-var">result</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-pragma">{-# SCC</span><span> </span><span class="hs-pragma">&quot;Digraph.reachable&quot;</span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-365"></span><span>                 </span><span class="annot"><span class="annottext">IntGraph -&gt; [Vertex] -&gt; [Vertex]
</span><a href="GHC.Data.Graph.Directed.html#reachable"><span class="hs-identifier hs-var">reachable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816716"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816713"><span class="hs-identifier hs-var">vs</span></a></span><span>
</span><span id="line-366"></span><span>        </span><span id="local-6989586621680816713"><span class="annot"><span class="annottext">vs :: [Vertex]
</span><a href="#local-6989586621680816713"><span class="hs-identifier hs-var hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816712"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680816712"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816712"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(node -&gt; Maybe Vertex) -&gt; [node] -&gt; [Maybe Vertex]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; node -&gt; Maybe Vertex
forall node. Graph node -&gt; node -&gt; Maybe Vertex
</span><a href="GHC.Data.Graph.Directed.html#gr_node_to_vertex"><span class="hs-identifier hs-var hs-var">gr_node_to_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816716"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[node]
</span><a href="#local-6989586621680816715"><span class="hs-identifier hs-var">froms</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-367"></span><span>
</span><span id="line-368"></span><span id="local-6989586621680816988"><span class="annot"><a href="GHC.Data.Graph.Directed.html#hasVertexG"><span class="hs-identifier hs-type">hasVertexG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816988"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680816988"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span><span>
</span><span id="line-369"></span><span id="hasVertexG"><span class="annot"><span class="annottext">hasVertexG :: forall node. Graph node -&gt; node -&gt; Bool
</span><a href="GHC.Data.Graph.Directed.html#hasVertexG"><span class="hs-identifier hs-var hs-var">hasVertexG</span></a></span></span><span> </span><span id="local-6989586621680816711"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816711"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span id="local-6989586621680816710"><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816710"><span class="hs-identifier hs-var">node</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Maybe Vertex -&gt; Bool
forall a. Maybe a -&gt; Bool
</span><a href="../../base/src/Data.Maybe.html#isJust"><span class="hs-identifier hs-var">isJust</span></a></span><span> </span><span class="annot"><span class="annottext">(Maybe Vertex -&gt; Bool) -&gt; Maybe Vertex -&gt; Bool
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node -&gt; node -&gt; Maybe Vertex
forall node. Graph node -&gt; node -&gt; Maybe Vertex
</span><a href="GHC.Data.Graph.Directed.html#gr_node_to_vertex"><span class="hs-identifier hs-var hs-var">gr_node_to_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816711"><span class="hs-identifier hs-var">graph</span></a></span><span> </span><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816710"><span class="hs-identifier hs-var">node</span></a></span><span>
</span><span id="line-370"></span><span>
</span><span id="line-371"></span><span id="local-6989586621680816708"><span class="annot"><a href="GHC.Data.Graph.Directed.html#verticesG"><span class="hs-identifier hs-type">verticesG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816708"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816708"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-372"></span><span id="verticesG"><span class="annot"><span class="annottext">verticesG :: forall node. Graph node -&gt; [node]
</span><a href="GHC.Data.Graph.Directed.html#verticesG"><span class="hs-identifier hs-var hs-var">verticesG</span></a></span></span><span> </span><span id="local-6989586621680816707"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816707"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; node) -&gt; [Vertex] -&gt; [node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816707"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([Vertex] -&gt; [node]) -&gt; [Vertex] -&gt; [node]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; [Vertex]
</span><a href="../../containers/src/Data.Graph.html#vertices"><span class="hs-identifier hs-var">vertices</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816707"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-373"></span><span>
</span><span id="line-374"></span><span id="local-6989586621680816984"><span class="annot"><a href="GHC.Data.Graph.Directed.html#edgesG"><span class="hs-identifier hs-type">edgesG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816984"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-type">Edge</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816984"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-375"></span><span id="edgesG"><span class="annot"><span class="annottext">edgesG :: forall node. Graph node -&gt; [Edge node]
</span><a href="GHC.Data.Graph.Directed.html#edgesG"><span class="hs-identifier hs-var hs-var">edgesG</span></a></span></span><span> </span><span id="local-6989586621680816705"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816705"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">((Vertex, Vertex) -&gt; Edge node)
-&gt; [(Vertex, Vertex)] -&gt; [Edge node]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="hs-special">(</span><span id="local-6989586621680816704"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816704"><span class="hs-identifier hs-var">v1</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816703"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816703"><span class="hs-identifier hs-var">v2</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">node -&gt; node -&gt; Edge node
forall node. node -&gt; node -&gt; Edge node
</span><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-var">Edge</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816702"><span class="hs-identifier hs-var">v2n</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816704"><span class="hs-identifier hs-var">v1</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex -&gt; node
</span><a href="#local-6989586621680816702"><span class="hs-identifier hs-var">v2n</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816703"><span class="hs-identifier hs-var">v2</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([(Vertex, Vertex)] -&gt; [Edge node])
-&gt; [(Vertex, Vertex)] -&gt; [Edge node]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; [(Vertex, Vertex)]
</span><a href="../../containers/src/Data.Graph.html#edges"><span class="hs-identifier hs-var">edges</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816705"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-376"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621680816702"><span class="annot"><span class="annottext">v2n :: Vertex -&gt; node
</span><a href="#local-6989586621680816702"><span class="hs-identifier hs-var hs-var">v2n</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816705"><span class="hs-identifier hs-var">graph</span></a></span><span>
</span><span id="line-377"></span><span>
</span><span id="line-378"></span><span id="local-6989586621680816981"><span class="annot"><a href="GHC.Data.Graph.Directed.html#transposeG"><span class="hs-identifier hs-type">transposeG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816981"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816981"><span class="hs-identifier hs-type">node</span></a></span></span><span>
</span><span id="line-379"></span><span id="transposeG"><span class="annot"><span class="annottext">transposeG :: forall node. Graph node -&gt; Graph node
</span><a href="GHC.Data.Graph.Directed.html#transposeG"><span class="hs-identifier hs-var hs-var">transposeG</span></a></span></span><span> </span><span id="local-6989586621680816700"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816700"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntGraph
-&gt; (Vertex -&gt; node) -&gt; (node -&gt; Maybe Vertex) -&gt; Graph node
forall node.
IntGraph
-&gt; (Vertex -&gt; node) -&gt; (node -&gt; Maybe Vertex) -&gt; Graph node
</span><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IntGraph -&gt; IntGraph
</span><a href="../../containers/src/Data.Graph.html#transposeG"><span class="hs-identifier hs-var">G.transposeG</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816700"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-380"></span><span>                         </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; Vertex -&gt; node
forall node. Graph node -&gt; Vertex -&gt; node
</span><a href="GHC.Data.Graph.Directed.html#gr_vertex_to_node"><span class="hs-identifier hs-var hs-var">gr_vertex_to_node</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816700"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-381"></span><span>                         </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; node -&gt; Maybe Vertex
forall node. Graph node -&gt; node -&gt; Maybe Vertex
</span><a href="GHC.Data.Graph.Directed.html#gr_node_to_vertex"><span class="hs-identifier hs-var hs-var">gr_node_to_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816700"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-382"></span><span>
</span><span id="line-383"></span><span id="local-6989586621680816979"><span class="annot"><a href="GHC.Data.Graph.Directed.html#emptyG"><span class="hs-identifier hs-type">emptyG</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816979"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span><span>
</span><span id="line-384"></span><span id="emptyG"><span class="annot"><span class="annottext">emptyG :: forall node. Graph node -&gt; Bool
</span><a href="GHC.Data.Graph.Directed.html#emptyG"><span class="hs-identifier hs-var hs-var">emptyG</span></a></span></span><span> </span><span id="local-6989586621680816699"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816699"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; Bool
</span><a href="GHC.Data.Graph.Directed.html#graphEmpty"><span class="hs-identifier hs-var">graphEmpty</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph node -&gt; IntGraph
forall node. Graph node -&gt; IntGraph
</span><a href="GHC.Data.Graph.Directed.html#gr_int_graph"><span class="hs-identifier hs-var hs-var">gr_int_graph</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816699"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-385"></span><span>
</span><span id="line-386"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      Showing Graphs
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-393"></span><span>
</span><span id="line-394"></span><span id="local-6989586621680816977"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621680816695"><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816977"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816977"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-395"></span><span>    </span><span id="local-6989586621680816692"><span class="annot"><span class="annottext">ppr :: Graph node -&gt; SDoc
</span><a href="#local-6989586621680816692"><span class="hs-identifier hs-var hs-var hs-var hs-var">ppr</span></a></span></span><span> </span><span id="local-6989586621680816691"><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816691"><span class="hs-identifier hs-var">graph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[SDoc] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#vcat"><span class="hs-identifier hs-var">vcat</span></a></span><span> </span><span class="hs-special">[</span><span>
</span><span id="line-396"></span><span>                  </span><span class="annot"><span class="annottext">SDoc -&gt; Vertex -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#hang"><span class="hs-identifier hs-var">hang</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Vertices:&quot;</span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">2</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[SDoc] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#vcat"><span class="hs-identifier hs-var">vcat</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(node -&gt; SDoc) -&gt; [node] -&gt; [SDoc]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">node -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">([node] -&gt; [SDoc]) -&gt; [node] -&gt; [SDoc]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node -&gt; [node]
forall node. Graph node -&gt; [node]
</span><a href="GHC.Data.Graph.Directed.html#verticesG"><span class="hs-identifier hs-var">verticesG</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816691"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-397"></span><span>                  </span><span class="annot"><span class="annottext">SDoc -&gt; Vertex -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#hang"><span class="hs-identifier hs-var">hang</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Edges:&quot;</span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">2</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[SDoc] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#vcat"><span class="hs-identifier hs-var">vcat</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Edge node -&gt; SDoc) -&gt; [Edge node] -&gt; [SDoc]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Edge node -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">([Edge node] -&gt; [SDoc]) -&gt; [Edge node] -&gt; [SDoc]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node -&gt; [Edge node]
forall node. Graph node -&gt; [Edge node]
</span><a href="GHC.Data.Graph.Directed.html#edgesG"><span class="hs-identifier hs-var">edgesG</span></a></span><span> </span><span class="annot"><span class="annottext">Graph node
</span><a href="#local-6989586621680816691"><span class="hs-identifier hs-var">graph</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-398"></span><span>                </span><span class="hs-special">]</span></span><span>
</span><span id="line-399"></span><span>
</span><span id="line-400"></span><span id="local-6989586621680816976"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621680816685"><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816976"><span class="hs-identifier hs-type">node</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-type">Edge</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816976"><span class="hs-identifier hs-type">node</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-401"></span><span>    </span><span id="local-6989586621680816682"><span class="annot"><span class="annottext">ppr :: Edge node -&gt; SDoc
</span><a href="#local-6989586621680816682"><span class="hs-identifier hs-var hs-var hs-var hs-var">ppr</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Edge"><span class="hs-identifier hs-type">Edge</span></a></span><span> </span><span id="local-6989586621680816681"><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816681"><span class="hs-identifier hs-var">from</span></a></span></span><span> </span><span id="local-6989586621680816680"><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816680"><span class="hs-identifier hs-var">to</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">node -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816681"><span class="hs-identifier hs-var">from</span></a></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%2B%3E"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;-&gt;&quot;</span></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%2B%3E"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">node -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">node
</span><a href="#local-6989586621680816680"><span class="hs-identifier hs-var">to</span></a></span></span><span>
</span><span id="line-402"></span><span>
</span><span id="line-403"></span><span class="annot"><a href="GHC.Data.Graph.Directed.html#graphEmpty"><span class="hs-identifier hs-type">graphEmpty</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier hs-type">G.Graph</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span><span>
</span><span id="line-404"></span><span id="graphEmpty"><span class="annot"><span class="annottext">graphEmpty :: IntGraph -&gt; Bool
</span><a href="GHC.Data.Graph.Directed.html#graphEmpty"><span class="hs-identifier hs-var hs-var">graphEmpty</span></a></span></span><span> </span><span id="local-6989586621680816678"><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816678"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816677"><span class="hs-identifier hs-var">lo</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Vertex -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816675"><span class="hs-identifier hs-var">hi</span></a></span><span>
</span><span id="line-405"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816677"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816677"><span class="hs-identifier hs-var">lo</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816675"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621680816675"><span class="hs-identifier hs-var">hi</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntGraph -&gt; (Vertex, Vertex)
forall i e. Array i e -&gt; (i, i)
</span><a href="../../base/src/GHC.Arr.html#bounds"><span class="hs-identifier hs-var">bounds</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816678"><span class="hs-identifier hs-var">g</span></a></span><span>
</span><span id="line-406"></span><span>
</span><span id="line-407"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*      IntGraphs
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-414"></span><span>
</span><span id="line-415"></span><span class="hs-keyword">type</span><span> </span><span id="IntGraph"><span class="annot"><a href="GHC.Data.Graph.Directed.html#IntGraph"><span class="hs-identifier hs-var">IntGraph</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier hs-type">G.Graph</span></a></span><span>
</span><span id="line-416"></span><span>
</span><span id="line-417"></span><span class="hs-comment">{-
------------------------------------------------------------
-- Depth first search numbering
------------------------------------------------------------
-}</span><span>
</span><span id="line-422"></span><span>
</span><span id="line-423"></span><span class="hs-comment">-- Data.Tree has flatten for Tree, but nothing for Forest</span><span>
</span><span id="line-424"></span><span id="local-6989586621680816973"><span class="annot"><a href="GHC.Data.Graph.Directed.html#preorderF"><span class="hs-identifier hs-type">preorderF</span></a></span><span>           </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#Forest"><span class="hs-identifier hs-type">Forest</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816973"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816973"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-425"></span><span id="preorderF"><span class="annot"><span class="annottext">preorderF :: forall a. Forest a -&gt; [a]
</span><a href="GHC.Data.Graph.Directed.html#preorderF"><span class="hs-identifier hs-var hs-var">preorderF</span></a></span></span><span> </span><span id="local-6989586621680816671"><span class="annot"><span class="annottext">Forest a
</span><a href="#local-6989586621680816671"><span class="hs-identifier hs-var">ts</span></a></span></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; [a]) -&gt; Forest a -&gt; [a]
forall (t :: * -&gt; *) a b. Foldable t =&gt; (a -&gt; [b]) -&gt; t a -&gt; [b]
</span><a href="../../base/src/Data.Foldable.html#concatMap"><span class="hs-identifier hs-var">concatMap</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [a]
forall a. Tree a -&gt; [a]
</span><a href="../../containers/src/Data.Tree.html#flatten"><span class="hs-identifier hs-var">flatten</span></a></span><span> </span><span class="annot"><span class="annottext">Forest a
</span><a href="#local-6989586621680816671"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-426"></span><span>
</span><span id="line-427"></span><span class="hs-comment">{-
------------------------------------------------------------
-- Finding reachable vertices
------------------------------------------------------------
-}</span><span>
</span><span id="line-432"></span><span>
</span><span id="line-433"></span><span class="hs-comment">-- This generalizes reachable which was found in Data.Graph</span><span>
</span><span id="line-434"></span><span class="annot"><a href="GHC.Data.Graph.Directed.html#reachable"><span class="hs-identifier hs-type">reachable</span></a></span><span>    </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#IntGraph"><span class="hs-identifier hs-type">IntGraph</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">Vertex</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-435"></span><span id="reachable"><span class="annot"><span class="annottext">reachable :: IntGraph -&gt; [Vertex] -&gt; [Vertex]
</span><a href="GHC.Data.Graph.Directed.html#reachable"><span class="hs-identifier hs-var hs-var">reachable</span></a></span></span><span> </span><span id="local-6989586621680816668"><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816668"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621680816667"><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816667"><span class="hs-identifier hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Forest Vertex -&gt; [Vertex]
forall a. Forest a -&gt; [a]
</span><a href="GHC.Data.Graph.Directed.html#preorderF"><span class="hs-identifier hs-var">preorderF</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">IntGraph -&gt; [Vertex] -&gt; Forest Vertex
</span><a href="../../containers/src/Data.Graph.html#dfs"><span class="hs-identifier hs-var">dfs</span></a></span><span> </span><span class="annot"><span class="annottext">IntGraph
</span><a href="#local-6989586621680816668"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621680816667"><span class="hs-identifier hs-var">vs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-436"></span><span>
</span><span id="line-437"></span><span class="hs-comment">{-
************************************************************************
*                                                                      *
*                         Classify Edge Types
*                                                                      *
************************************************************************
-}</span><span>
</span><span id="line-444"></span><span>
</span><span id="line-445"></span><span class="hs-comment">-- Remark: While we could generalize this algorithm this comes at a runtime</span><span>
</span><span id="line-446"></span><span class="hs-comment">-- cost and with no advantages. If you find yourself using this with graphs</span><span>
</span><span id="line-447"></span><span class="hs-comment">-- not easily represented using Int nodes please consider rewriting this</span><span>
</span><span id="line-448"></span><span class="hs-comment">-- using the more general Graph type.</span><span>
</span><span id="line-449"></span><span>
</span><span id="line-450"></span><span class="hs-comment">-- | Edge direction based on DFS Classification</span><span>
</span><span id="line-451"></span><span class="hs-keyword">data</span><span> </span><span id="EdgeType"><span class="annot"><a href="GHC.Data.Graph.Directed.html#EdgeType"><span class="hs-identifier hs-var">EdgeType</span></a></span></span><span>
</span><span id="line-452"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span id="Forward"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Forward"><span class="hs-identifier hs-var">Forward</span></a></span></span><span>
</span><span id="line-453"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span id="Cross"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Cross"><span class="hs-identifier hs-var">Cross</span></a></span></span><span>
</span><span id="line-454"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span id="Backward"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Backward"><span class="hs-identifier hs-var">Backward</span></a></span></span><span> </span><span class="hs-comment">-- ^ Loop back towards the root node.</span><span>
</span><span id="line-455"></span><span>             </span><span class="hs-comment">-- Eg backjumps in loops</span><span>
</span><span id="line-456"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span id="SelfLoop"><span class="annot"><a href="GHC.Data.Graph.Directed.html#SelfLoop"><span class="hs-identifier hs-var">SelfLoop</span></a></span></span><span> </span><span class="hs-comment">-- ^ v -&gt; v</span><span>
</span><span id="line-457"></span><span>   </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816658"><span id="local-6989586621680816660"><span class="annot"><span class="annottext">EdgeType -&gt; EdgeType -&gt; Bool
(EdgeType -&gt; EdgeType -&gt; Bool)
-&gt; (EdgeType -&gt; EdgeType -&gt; Bool) -&gt; Eq EdgeType
forall a. (a -&gt; a -&gt; Bool) -&gt; (a -&gt; a -&gt; Bool) -&gt; Eq a
/= :: EdgeType -&gt; EdgeType -&gt; Bool
$c/= :: EdgeType -&gt; EdgeType -&gt; Bool
== :: EdgeType -&gt; EdgeType -&gt; Bool
$c== :: EdgeType -&gt; EdgeType -&gt; Bool
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Eq</span></span></span></span><span class="hs-special">,</span><span id="local-6989586621680816638"><span id="local-6989586621680816640"><span id="local-6989586621680816643"><span id="local-6989586621680816646"><span id="local-6989586621680816649"><span id="local-6989586621680816651"><span id="local-6989586621680816653"><span class="annot"><span class="annottext">Eq EdgeType
Eq EdgeType
-&gt; (EdgeType -&gt; EdgeType -&gt; Ordering)
-&gt; (EdgeType -&gt; EdgeType -&gt; Bool)
-&gt; (EdgeType -&gt; EdgeType -&gt; Bool)
-&gt; (EdgeType -&gt; EdgeType -&gt; Bool)
-&gt; (EdgeType -&gt; EdgeType -&gt; Bool)
-&gt; (EdgeType -&gt; EdgeType -&gt; EdgeType)
-&gt; (EdgeType -&gt; EdgeType -&gt; EdgeType)
-&gt; Ord EdgeType
EdgeType -&gt; EdgeType -&gt; Bool
EdgeType -&gt; EdgeType -&gt; Ordering
EdgeType -&gt; EdgeType -&gt; EdgeType
forall a.
Eq a
-&gt; (a -&gt; a -&gt; Ordering)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; a)
-&gt; (a -&gt; a -&gt; a)
-&gt; Ord a
min :: EdgeType -&gt; EdgeType -&gt; EdgeType
$cmin :: EdgeType -&gt; EdgeType -&gt; EdgeType
max :: EdgeType -&gt; EdgeType -&gt; EdgeType
$cmax :: EdgeType -&gt; EdgeType -&gt; EdgeType
&gt;= :: EdgeType -&gt; EdgeType -&gt; Bool
$c&gt;= :: EdgeType -&gt; EdgeType -&gt; Bool
&gt; :: EdgeType -&gt; EdgeType -&gt; Bool
$c&gt; :: EdgeType -&gt; EdgeType -&gt; Bool
&lt;= :: EdgeType -&gt; EdgeType -&gt; Bool
$c&lt;= :: EdgeType -&gt; EdgeType -&gt; Bool
&lt; :: EdgeType -&gt; EdgeType -&gt; Bool
$c&lt; :: EdgeType -&gt; EdgeType -&gt; Bool
compare :: EdgeType -&gt; EdgeType -&gt; Ordering
$ccompare :: EdgeType -&gt; EdgeType -&gt; Ordering
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Ord</span></span></span></span></span></span></span></span></span><span class="hs-special">)</span><span>
</span><span id="line-458"></span><span>
</span><span id="line-459"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621680816634"><span class="annot"><a href="GHC.Utils.Outputable.html#Outputable"><span class="hs-identifier hs-type">Outputable</span></a></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#EdgeType"><span class="hs-identifier hs-type">EdgeType</span></a></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-460"></span><span>  </span><span id="local-6989586621680816633"><span class="annot"><span class="annottext">ppr :: EdgeType -&gt; SDoc
</span><a href="#local-6989586621680816633"><span class="hs-identifier hs-var hs-var hs-var hs-var">ppr</span></a></span></span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Forward"><span class="hs-identifier hs-var">Forward</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Forward&quot;</span></span><span>
</span><span id="line-461"></span><span>  </span><span class="annot"><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Cross"><span class="hs-identifier hs-var">Cross</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Cross&quot;</span></span><span>
</span><span id="line-462"></span><span>  </span><span class="annot"><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Backward"><span class="hs-identifier hs-var">Backward</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Backward&quot;</span></span><span>
</span><span id="line-463"></span><span>  </span><span class="annot"><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#SelfLoop"><span class="hs-identifier hs-var">SelfLoop</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;SelfLoop&quot;</span></span><span>
</span><span id="line-464"></span><span>
</span><span id="line-465"></span><span class="hs-keyword">newtype</span><span> </span><span id="Time"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-var">Time</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Time"><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-var">Time</span></a></span></span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816626"><span id="local-6989586621680816630"><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
(Time -&gt; Time -&gt; Bool) -&gt; (Time -&gt; Time -&gt; Bool) -&gt; Eq Time
forall a. (a -&gt; a -&gt; Bool) -&gt; (a -&gt; a -&gt; Bool) -&gt; Eq a
/= :: Time -&gt; Time -&gt; Bool
$c/= :: Time -&gt; Time -&gt; Bool
== :: Time -&gt; Time -&gt; Bool
$c== :: Time -&gt; Time -&gt; Bool
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Eq</span></span></span></span><span class="hs-special">,</span><span id="local-6989586621680816595"><span id="local-6989586621680816599"><span id="local-6989586621680816603"><span id="local-6989586621680816607"><span id="local-6989586621680816611"><span id="local-6989586621680816615"><span id="local-6989586621680816619"><span class="annot"><span class="annottext">Eq Time
Eq Time
-&gt; (Time -&gt; Time -&gt; Ordering)
-&gt; (Time -&gt; Time -&gt; Bool)
-&gt; (Time -&gt; Time -&gt; Bool)
-&gt; (Time -&gt; Time -&gt; Bool)
-&gt; (Time -&gt; Time -&gt; Bool)
-&gt; (Time -&gt; Time -&gt; Time)
-&gt; (Time -&gt; Time -&gt; Time)
-&gt; Ord Time
Time -&gt; Time -&gt; Bool
Time -&gt; Time -&gt; Ordering
Time -&gt; Time -&gt; Time
forall a.
Eq a
-&gt; (a -&gt; a -&gt; Ordering)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; Bool)
-&gt; (a -&gt; a -&gt; a)
-&gt; (a -&gt; a -&gt; a)
-&gt; Ord a
min :: Time -&gt; Time -&gt; Time
$cmin :: Time -&gt; Time -&gt; Time
max :: Time -&gt; Time -&gt; Time
$cmax :: Time -&gt; Time -&gt; Time
&gt;= :: Time -&gt; Time -&gt; Bool
$c&gt;= :: Time -&gt; Time -&gt; Bool
&gt; :: Time -&gt; Time -&gt; Bool
$c&gt; :: Time -&gt; Time -&gt; Bool
&lt;= :: Time -&gt; Time -&gt; Bool
$c&lt;= :: Time -&gt; Time -&gt; Bool
&lt; :: Time -&gt; Time -&gt; Bool
$c&lt; :: Time -&gt; Time -&gt; Bool
compare :: Time -&gt; Time -&gt; Ordering
$ccompare :: Time -&gt; Time -&gt; Ordering
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Ord</span></span></span></span></span></span></span></span></span><span class="hs-special">,</span><span id="local-6989586621680816566"><span id="local-6989586621680816570"><span id="local-6989586621680816574"><span id="local-6989586621680816578"><span id="local-6989586621680816582"><span id="local-6989586621680816586"><span id="local-6989586621680816590"><span class="annot"><span class="annottext">Integer -&gt; Time
Time -&gt; Time
Time -&gt; Time -&gt; Time
(Time -&gt; Time -&gt; Time)
-&gt; (Time -&gt; Time -&gt; Time)
-&gt; (Time -&gt; Time -&gt; Time)
-&gt; (Time -&gt; Time)
-&gt; (Time -&gt; Time)
-&gt; (Time -&gt; Time)
-&gt; (Integer -&gt; Time)
-&gt; Num Time
forall a.
(a -&gt; a -&gt; a)
-&gt; (a -&gt; a -&gt; a)
-&gt; (a -&gt; a -&gt; a)
-&gt; (a -&gt; a)
-&gt; (a -&gt; a)
-&gt; (a -&gt; a)
-&gt; (Integer -&gt; a)
-&gt; Num a
fromInteger :: Integer -&gt; Time
$cfromInteger :: Integer -&gt; Time
signum :: Time -&gt; Time
$csignum :: Time -&gt; Time
abs :: Time -&gt; Time
$cabs :: Time -&gt; Time
negate :: Time -&gt; Time
$cnegate :: Time -&gt; Time
* :: Time -&gt; Time -&gt; Time
$c* :: Time -&gt; Time -&gt; Time
- :: Time -&gt; Time -&gt; Time
$c- :: Time -&gt; Time -&gt; Time
+ :: Time -&gt; Time -&gt; Time
$c+ :: Time -&gt; Time -&gt; Time
</span><a href="../../base/src/GHC.Num.html#Num"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Num</span></a></span></span></span></span></span></span></span></span><span class="hs-special">,</span><span id="local-6989586621680816555"><span id="local-6989586621680816560"><span class="annot"><span class="annottext">Rational -&gt; Time -&gt; SDoc
Time -&gt; SDoc
(Time -&gt; SDoc) -&gt; (Rational -&gt; Time -&gt; SDoc) -&gt; Outputable Time
forall a. (a -&gt; SDoc) -&gt; (Rational -&gt; a -&gt; SDoc) -&gt; Outputable a
pprPrec :: Rational -&gt; Time -&gt; SDoc
$cpprPrec :: Rational -&gt; Time -&gt; SDoc
ppr :: Time -&gt; SDoc
$cppr :: Time -&gt; SDoc
</span><a href="#local-6989586621680816555"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Outputable</span></a></span></span></span><span class="hs-special">)</span><span>
</span><span id="line-466"></span><span>
</span><span id="line-467"></span><span class="hs-comment">--Allow for specialization</span><span>
</span><span id="line-468"></span><span class="hs-pragma">{-# INLINEABLE</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#classifyEdges"><span class="hs-pragma hs-type">classifyEdges</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-469"></span><span>
</span><span id="line-470"></span><span class="hs-comment">-- | Given a start vertex, a way to get successors from a node</span><span>
</span><span id="line-471"></span><span class="hs-comment">-- and a list of (directed) edges classify the types of edges.</span><span>
</span><span id="line-472"></span><span class="annot"><a href="GHC.Data.Graph.Directed.html#classifyEdges"><span class="hs-identifier hs-type">classifyEdges</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-keyword">forall</span><span> </span><span id="local-6989586621680816966"><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span></span><span class="hs-operator">.</span><span> </span><span class="annot"><a href="GHC.Types.Unique.html#Uniquable"><span class="hs-identifier hs-type">Uniquable</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-473"></span><span>              </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">,</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#EdgeType"><span class="hs-identifier hs-type">EdgeType</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span><span>
</span><span id="line-474"></span><span id="classifyEdges"><span class="annot"><span class="annottext">classifyEdges :: forall key.
Uniquable key =&gt;
key -&gt; (key -&gt; [key]) -&gt; [(key, key)] -&gt; [((key, key), EdgeType)]
</span><a href="GHC.Data.Graph.Directed.html#classifyEdges"><span class="hs-identifier hs-var hs-var">classifyEdges</span></a></span></span><span> </span><span id="local-6989586621680816528"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816528"><span class="hs-identifier hs-var">root</span></a></span></span><span> </span><span id="local-6989586621680816527"><span class="annot"><span class="annottext">key -&gt; [key]
</span><a href="#local-6989586621680816527"><span class="hs-identifier hs-var">getSucc</span></a></span></span><span> </span><span id="local-6989586621680816526"><span class="annot"><span class="annottext">[(key, key)]
</span><a href="#local-6989586621680816526"><span class="hs-identifier hs-var">edges</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-475"></span><span>    </span><span class="hs-comment">--let uqe (from,to) = (getUnique from, getUnique to)</span><span>
</span><span id="line-476"></span><span>    </span><span class="hs-comment">--in pprTrace &quot;Edges:&quot; (ppr $ map uqe edges) $</span><span>
</span><span id="line-477"></span><span>    </span><span class="annot"><span class="annottext">[(key, key)] -&gt; [EdgeType] -&gt; [((key, key), EdgeType)]
forall a b. [a] -&gt; [b] -&gt; [(a, b)]
</span><a href="../../base/src/GHC.List.html#zip"><span class="hs-identifier hs-var">zip</span></a></span><span> </span><span class="annot"><span class="annottext">[(key, key)]
</span><a href="#local-6989586621680816526"><span class="hs-identifier hs-var">edges</span></a></span><span> </span><span class="annot"><span class="annottext">([EdgeType] -&gt; [((key, key), EdgeType)])
-&gt; [EdgeType] -&gt; [((key, key), EdgeType)]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">((key, key) -&gt; EdgeType) -&gt; [(key, key)] -&gt; [EdgeType]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">(key, key) -&gt; EdgeType
</span><a href="#local-6989586621680816525"><span class="hs-identifier hs-var">classify</span></a></span><span> </span><span class="annot"><span class="annottext">[(key, key)]
</span><a href="#local-6989586621680816526"><span class="hs-identifier hs-var">edges</span></a></span><span>
</span><span id="line-478"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-479"></span><span>    </span><span class="hs-special">(</span><span id="local-6989586621680816523"><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816523"><span class="hs-identifier hs-var">_time</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816522"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816522"><span class="hs-identifier hs-var">starts</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621680816521"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816521"><span class="hs-identifier hs-var">ends</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Time, UniqFM key Time, UniqFM key Time)
-&gt; key -&gt; (Time, UniqFM key Time, UniqFM key Time)
</span><a href="#local-6989586621680816520"><span class="hs-identifier hs-var">addTimes</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Time
</span><span class="hs-number">0</span></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
forall key elt. UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#emptyUFM"><span class="hs-identifier hs-var">emptyUFM</span></a></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
forall key elt. UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#emptyUFM"><span class="hs-identifier hs-var">emptyUFM</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816528"><span class="hs-identifier hs-var">root</span></a></span><span>
</span><span id="line-480"></span><span>    </span><span class="annot"><a href="#local-6989586621680816525"><span class="hs-identifier hs-type">classify</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">,</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#EdgeType"><span class="hs-identifier hs-type">EdgeType</span></a></span><span>
</span><span id="line-481"></span><span>    </span><span id="local-6989586621680816525"><span class="annot"><span class="annottext">classify :: (key, key) -&gt; EdgeType
</span><a href="#local-6989586621680816525"><span class="hs-identifier hs-var hs-var">classify</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816518"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680816517"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-482"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816516"><span class="hs-identifier hs-var">startFrom</span></a></span><span> </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&lt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816514"><span class="hs-identifier hs-var">startTo</span></a></span><span>
</span><span id="line-483"></span><span>      </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816513"><span class="hs-identifier hs-var">endFrom</span></a></span><span>   </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816512"><span class="hs-identifier hs-var">endTo</span></a></span><span>
</span><span id="line-484"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Forward"><span class="hs-identifier hs-var">Forward</span></a></span><span>
</span><span id="line-485"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816516"><span class="hs-identifier hs-var">startFrom</span></a></span><span> </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816514"><span class="hs-identifier hs-var">startTo</span></a></span><span>
</span><span id="line-486"></span><span>      </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816513"><span class="hs-identifier hs-var">endFrom</span></a></span><span>   </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&lt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816512"><span class="hs-identifier hs-var">endTo</span></a></span><span>
</span><span id="line-487"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Backward"><span class="hs-identifier hs-var">Backward</span></a></span><span>
</span><span id="line-488"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816516"><span class="hs-identifier hs-var">startFrom</span></a></span><span> </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816514"><span class="hs-identifier hs-var">startTo</span></a></span><span>
</span><span id="line-489"></span><span>      </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816513"><span class="hs-identifier hs-var">endFrom</span></a></span><span>   </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816512"><span class="hs-identifier hs-var">endTo</span></a></span><span>
</span><span id="line-490"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#Cross"><span class="hs-identifier hs-var">Cross</span></a></span><span>
</span><span id="line-491"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span><span> </span><span class="annot"><span class="annottext">Unique -&gt; Unique -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span><span>
</span><span id="line-492"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">EdgeType
</span><a href="GHC.Data.Graph.Directed.html#SelfLoop"><span class="hs-identifier hs-var">SelfLoop</span></a></span><span>
</span><span id="line-493"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>
</span><span id="line-494"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc -&gt; EdgeType
forall a. HasCallStack =&gt; [Char] -&gt; SDoc -&gt; a
</span><a href="GHC.Utils.Outputable.html#pprPanic"><span class="hs-identifier hs-var">pprPanic</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Failed to classify edge of Graph&quot;</span></span><span>
</span><span id="line-495"></span><span>                 </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Unique, Unique) -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-496"></span><span>
</span><span id="line-497"></span><span>      </span><span class="hs-keyword">where</span><span>
</span><span id="line-498"></span><span>        </span><span id="local-6989586621680816496"><span class="annot"><span class="annottext">getTime :: UniqFM key elt -&gt; key -&gt; elt
</span><a href="#local-6989586621680816496"><span class="hs-identifier hs-var hs-var">getTime</span></a></span></span><span> </span><span id="local-6989586621680816495"><span class="annot"><span class="annottext">UniqFM key elt
</span><a href="#local-6989586621680816495"><span class="hs-identifier hs-var">event</span></a></span></span><span> </span><span id="local-6989586621680816494"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816494"><span class="hs-identifier hs-var">node</span></a></span></span><span>
</span><span id="line-499"></span><span>          </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Just"><span class="hs-identifier hs-type">Just</span></a></span><span> </span><span id="local-6989586621680816493"><span class="annot"><span class="annottext">elt
</span><a href="#local-6989586621680816493"><span class="hs-identifier hs-var">time</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">UniqFM key elt -&gt; key -&gt; Maybe elt
forall key elt. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; Maybe elt
</span><a href="GHC.Types.Unique.FM.html#lookupUFM"><span class="hs-identifier hs-var">lookupUFM</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key elt
</span><a href="#local-6989586621680816495"><span class="hs-identifier hs-var">event</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816494"><span class="hs-identifier hs-var">node</span></a></span><span>
</span><span id="line-500"></span><span>          </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">elt
</span><a href="#local-6989586621680816493"><span class="hs-identifier hs-var">time</span></a></span><span>
</span><span id="line-501"></span><span>          </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>
</span><span id="line-502"></span><span>          </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Char] -&gt; SDoc -&gt; elt
forall a. HasCallStack =&gt; [Char] -&gt; SDoc -&gt; a
</span><a href="GHC.Utils.Outputable.html#pprPanic"><span class="hs-identifier hs-var">pprPanic</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;Failed to classify edge of CFG - not not timed&quot;</span></span><span>
</span><span id="line-503"></span><span>            </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Char] -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#text"><span class="hs-identifier hs-var">text</span></a></span><span> </span><span class="annot"><span class="annottext">[Char]
</span><span class="hs-string">&quot;edges&quot;</span></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%3E"><span class="hs-operator hs-var">&lt;&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">(Unique, Unique) -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">key -&gt; Unique
forall a. Uniquable a =&gt; a -&gt; Unique
</span><a href="GHC.Types.Unique.html#getUnique"><span class="hs-identifier hs-var">getUnique</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-504"></span><span>                          </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%2B%3E"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816522"><span class="hs-identifier hs-var">starts</span></a></span><span> </span><span class="annot"><span class="annottext">SDoc -&gt; SDoc -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#%3C%2B%3E"><span class="hs-operator hs-var">&lt;+&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; SDoc
forall a. Outputable a =&gt; a -&gt; SDoc
</span><a href="GHC.Utils.Outputable.html#ppr"><span class="hs-identifier hs-var">ppr</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816521"><span class="hs-identifier hs-var">ends</span></a></span><span> </span><span class="hs-special">)</span><span>
</span><span id="line-505"></span><span>        </span><span id="local-6989586621680816516"><span class="annot"><span class="annottext">startFrom :: Time
</span><a href="#local-6989586621680816516"><span class="hs-identifier hs-var hs-var">startFrom</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time
forall {key} {elt}. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; elt
</span><a href="#local-6989586621680816496"><span class="hs-identifier hs-var">getTime</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816522"><span class="hs-identifier hs-var">starts</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span><span>
</span><span id="line-506"></span><span>        </span><span id="local-6989586621680816514"><span class="annot"><span class="annottext">startTo :: Time
</span><a href="#local-6989586621680816514"><span class="hs-identifier hs-var hs-var">startTo</span></a></span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time
forall {key} {elt}. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; elt
</span><a href="#local-6989586621680816496"><span class="hs-identifier hs-var">getTime</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816522"><span class="hs-identifier hs-var">starts</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span><span>
</span><span id="line-507"></span><span>        </span><span id="local-6989586621680816513"><span class="annot"><span class="annottext">endFrom :: Time
</span><a href="#local-6989586621680816513"><span class="hs-identifier hs-var hs-var">endFrom</span></a></span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time
forall {key} {elt}. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; elt
</span><a href="#local-6989586621680816496"><span class="hs-identifier hs-var">getTime</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816521"><span class="hs-identifier hs-var">ends</span></a></span><span>   </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816518"><span class="hs-identifier hs-var">from</span></a></span><span>
</span><span id="line-508"></span><span>        </span><span id="local-6989586621680816512"><span class="annot"><span class="annottext">endTo :: Time
</span><a href="#local-6989586621680816512"><span class="hs-identifier hs-var hs-var">endTo</span></a></span></span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time
forall {key} {elt}. Uniquable key =&gt; UniqFM key elt -&gt; key -&gt; elt
</span><a href="#local-6989586621680816496"><span class="hs-identifier hs-var">getTime</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816521"><span class="hs-identifier hs-var">ends</span></a></span><span>   </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816517"><span class="hs-identifier hs-var">to</span></a></span><span>
</span><span id="line-509"></span><span>
</span><span id="line-510"></span><span>    </span><span class="annot"><a href="#local-6989586621680816520"><span class="hs-identifier hs-type">addTimes</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span>
</span><span id="line-511"></span><span>             </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="GHC.Types.Unique.FM.html#UniqFM"><span class="hs-identifier hs-type">UniqFM</span></a></span><span> </span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span> </span><span class="annot"><a href="GHC.Data.Graph.Directed.html#Time"><span class="hs-identifier hs-type">Time</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-512"></span><span>    </span><span id="local-6989586621680816520"><span class="annot"><span class="annottext">addTimes :: (Time, UniqFM key Time, UniqFM key Time)
-&gt; key -&gt; (Time, UniqFM key Time, UniqFM key Time)
</span><a href="#local-6989586621680816520"><span class="hs-identifier hs-var hs-var">addTimes</span></a></span></span><span> </span><span class="hs-special">(</span><span id="local-6989586621680816487"><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816487"><span class="hs-identifier hs-var">time</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680816486"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816486"><span class="hs-identifier hs-var">starts</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680816485"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816485"><span class="hs-identifier hs-var">ends</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621680816484"><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816484"><span class="hs-identifier hs-var">n</span></a></span></span><span>
</span><span id="line-513"></span><span>      </span><span class="hs-comment">--Dont reenter nodes</span><span>
</span><span id="line-514"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">key -&gt; UniqFM key Time -&gt; Bool
forall key elt. Uniquable key =&gt; key -&gt; UniqFM key elt -&gt; Bool
</span><a href="GHC.Types.Unique.FM.html#elemUFM"><span class="hs-identifier hs-var">elemUFM</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816484"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816486"><span class="hs-identifier hs-var">starts</span></a></span><span>
</span><span id="line-515"></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816487"><span class="hs-identifier hs-var">time</span></a></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816486"><span class="hs-identifier hs-var">starts</span></a></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816485"><span class="hs-identifier hs-var">ends</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-516"></span><span>      </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-517"></span><span>        </span><span class="hs-keyword">let</span><span>
</span><span id="line-518"></span><span>          </span><span id="local-6989586621680816481"><span class="annot"><span class="annottext">starts' :: UniqFM key Time
</span><a href="#local-6989586621680816481"><span class="hs-identifier hs-var hs-var">starts'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time -&gt; UniqFM key Time
forall key elt.
Uniquable key =&gt;
UniqFM key elt -&gt; key -&gt; elt -&gt; UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#addToUFM"><span class="hs-identifier hs-var">addToUFM</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816486"><span class="hs-identifier hs-var">starts</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816484"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816487"><span class="hs-identifier hs-var">time</span></a></span><span>
</span><span id="line-519"></span><span>          </span><span id="local-6989586621680816477"><span class="annot"><span class="annottext">time' :: Time
</span><a href="#local-6989586621680816477"><span class="hs-identifier hs-var hs-var">time'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816487"><span class="hs-identifier hs-var">time</span></a></span><span> </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Time
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Time
</span><span class="hs-number">1</span></span><span>
</span><span id="line-520"></span><span>          </span><span id="local-6989586621680816475"><span class="annot"><span class="annottext">succs :: [key]
</span><a href="#local-6989586621680816475"><span class="hs-identifier hs-var hs-var">succs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">key -&gt; [key]
</span><a href="#local-6989586621680816527"><span class="hs-identifier hs-var">getSucc</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816484"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621680816966"><span class="hs-identifier hs-type">key</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-521"></span><span>          </span><span class="hs-special">(</span><span id="local-6989586621680816473"><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816473"><span class="hs-identifier hs-var">time''</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680816472"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816472"><span class="hs-identifier hs-var">starts''</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621680816471"><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816471"><span class="hs-identifier hs-var">ends'</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">((Time, UniqFM key Time, UniqFM key Time)
 -&gt; key -&gt; (Time, UniqFM key Time, UniqFM key Time))
-&gt; (Time, UniqFM key Time, UniqFM key Time)
-&gt; [key]
-&gt; (Time, UniqFM key Time, UniqFM key Time)
forall (t :: * -&gt; *) b a.
Foldable t =&gt;
(b -&gt; a -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl%27"><span class="hs-identifier hs-var">foldl'</span></a></span><span> </span><span class="annot"><span class="annottext">(Time, UniqFM key Time, UniqFM key Time)
-&gt; key -&gt; (Time, UniqFM key Time, UniqFM key Time)
</span><a href="#local-6989586621680816520"><span class="hs-identifier hs-var">addTimes</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816477"><span class="hs-identifier hs-var">time'</span></a></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816481"><span class="hs-identifier hs-var">starts'</span></a></span><span class="hs-special">,</span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816485"><span class="hs-identifier hs-var">ends</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[key]
</span><a href="#local-6989586621680816475"><span class="hs-identifier hs-var">succs</span></a></span><span>
</span><span id="line-522"></span><span>          </span><span id="local-6989586621680816468"><span class="annot"><span class="annottext">ends'' :: UniqFM key Time
</span><a href="#local-6989586621680816468"><span class="hs-identifier hs-var hs-var">ends''</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time -&gt; key -&gt; Time -&gt; UniqFM key Time
forall key elt.
Uniquable key =&gt;
UniqFM key elt -&gt; key -&gt; elt -&gt; UniqFM key elt
</span><a href="GHC.Types.Unique.FM.html#addToUFM"><span class="hs-identifier hs-var">addToUFM</span></a></span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816471"><span class="hs-identifier hs-var">ends'</span></a></span><span> </span><span class="annot"><span class="annottext">key
</span><a href="#local-6989586621680816484"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816473"><span class="hs-identifier hs-var">time''</span></a></span><span>
</span><span id="line-523"></span><span>        </span><span class="hs-keyword">in</span><span>
</span><span id="line-524"></span><span>        </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Time
</span><a href="#local-6989586621680816473"><span class="hs-identifier hs-var">time''</span></a></span><span> </span><span class="annot"><span class="annottext">Time -&gt; Time -&gt; Time
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Time
</span><span class="hs-number">1</span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816472"><span class="hs-identifier hs-var">starts''</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">UniqFM key Time
</span><a href="#local-6989586621680816468"><span class="hs-identifier hs-var">ends''</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-525"></span></pre></body></html>